BOJ 1764 - 듣보잡

문제 링크

문제#

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력#

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력#

듣보잡의 수와 그 명단을 사전순으로 출력한다.

풀이#

듣도 못한 사람과 보도 못한 사람의 교집합을 구하는 문제다. 그래서 한쪽 목록을 집합에 넣어 두고, 다른 목록을 읽으면서 집합에 있는 이름만 모으면 된다.

현재 코드는 교집합에 속한 이름들을 별도로 저장한 뒤 사전순으로 정렬해서 출력한다. 결국 membership check와 마지막 정렬 두 단계로 깔끔하게 나뉜다.

코드#

#include <iostream>
#include <set>
using namespace std;
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int N, M;
	cin >> N >> M;
 
	set<string> n;
 
	string name;
	for (int i = 0; i < N; i++) {
		cin >> name;
		n.insert(name);
	}
 
	int dbj = 0;
	set<string> dbjname;
 
	for (int j = 0; j < M; j++) {
		cin >> name;
		if (n.count(name)) {
			dbj++;
			dbjname.insert(name);
		}
	}
 
	cout << dbj << '\n';
	for (auto k = dbjname.begin(); k != dbjname.end(); k++)
		cout << *k << '\n';
 
	return 0;
}

복잡도#

• 시간 복잡도: 이름을 집합에 넣고 결과를 정렬하므로 $O((N + M) \log (N + M))$이다.
• 공간 복잡도: 이름 집합과 결과 목록을 저장하므로 $O(N + M)$이다.

마무리#

두 이름 목록의 교집합을 찾고 사전순으로 출력하는 문제다. 집합에 한쪽 목록을 저장해 두면 다른 목록을 읽을 때 공통 이름만 쉽게 골라낼 수 있다.