문제
BOJ 5089 - Travelling Salesman
매 주 방문한 도시 이름
n개가 주어질 때, 중복을 제거한 서로 다른 도시 수를Week i 개수형식으로 출력한다.n=0이면 종료.
풀이
set<string>에 도시명을 삽입해 중복을 자동으로 제거한 뒤 크기를 출력한다. 도시명에 공백이 포함될 수 있어 getline으로 한 줄 단위로 읽고, 앞선 cin 이후에는 cin.ignore()로 개행을 버린다.
코드
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
int n, week = 1;
while (cin >> n && n != 0) {
cin.ignore();
set<string> cities;
for (int i = 0; i < n; i++) {
string cityName;
getline(cin, cityName);
cities.insert(cityName);
}
cout << "Week " << week++ << " " << cities.size() << endl;
}
return 0;
}복잡도
- 시간: O(n log n) (n: 도시 수, set 삽입)
- 공간: O(n)