https://www.acmicpc.net/problem/1764
문제
> 명단에 듣도못한사람과 보도못한 사람이 각각 주어진다.
> 듣도보도 못한사람의 이름을 사전순으로 출력하라.접근
듣도못한 사람과 보도못한 사람을 map으로 정렬한다.
겹치는 사람을 찾고 이를 비교해 사전순으로 출력한다.
문제해결
> map으로 듣도못한 사람을 key로 value값은 1로해서 받는다.
> 보도못한 사람을 입렵받아 map에 추가하는데 보도못한사람과 겹치면 그 이름을 저장함
> 저장된 듣도보다 못한 사람의 수와 이름을 각각 출력한다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M;
cin >> N >> M;
string name;
map<string, int> unknown;
vector<string> result;
while (N--)
{
cin >> name;
unknown[name] = 1;
}
while (M--)
{
cin >> name;
if (unknown[name] == 1)
{
result.push_back(name);
}
}
sort(result.begin(), result.end());
cout << result.size() << '\n';
for (string s : result)
{
cout << s << '\n';
}
}
후기
반복문으로 완전탐색 했더니 런타임에러로 계속 틀렸다.
친구의 조언으로 map을 사용하여 했더니 성공했다.
완전탐색의 시간복잡도가 O(n)로 최악의 복잡도를 가진다고 한다. 하지만 map을 사용하면 O(log n)의 복잡도로 탐색범위가 절반줄어든다고 한다.
