[C++] 백준 1764: 듣보잡

문제

[C++] 백준 1764: 듣보잡 SILVER 4
https://www.acmicpc.net/problem/1764

 

---

 

접근 방법

이 문제는 듣도 못한 사람 N명 + 보도 못한 사람 M명이 주어졌을 때, 두 목록에 모두 속하는 사람(= 듣보잡) 을 찾는 문제다.

 

즉, 간단히 말하면

문자열 집합 A와 집합 B의 교집합을 구한 뒤, 그 결과를 사전 순으로 정렬해서 출력하는 문제.

 

풀이 아이디어는 이렇게 잡았다.

1. 먼저 듣도 못한 사람 N명을 입력받으면서 map<string, int> who에 이름을 저장한다.
   • 이름을 key, 값을 1로 저장 → 존재 여부 체크용
2. 다음으로 보도 못한 사람 M명을 입력받으면서
   • who[str] == 1이면 듣도 보도 못한 사람이므로 ret 벡터에 push.
3. ret에 모아둔 이름들을 sort로 사전 순 정렬한 뒤,
   • 개수 출력
   • 한 줄씩 이름 출력

map은 내부적으로 균형 이진 트리라서, 이름 1개를 넣거나 찾는 데 O(log N) 시간이 걸리고,
이 정도면 N, M이 커도 충분히 통과할 수 있다.

 

구현 시 주의할 점

• 교집합만 따로 모으기 위해 ret 벡터를 사용하고,
  마지막에 sort(ret.begin(), ret.end());로 정렬한 뒤 출력해야 한다.
• 시간 초과에 유의하여 map을 사용해야 한다.

 

---

 

코드

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0, m = 0;
	cin >> n >> m;

	map<string, int> who;
	for (int i = 0; i < n; i++)
	{
		string str = "";
		cin >> str;

		who[str] = 1;
	}
	
	vector<string> ret;
	for (int i = 0; i < m; i++)
	{
		string str = "";
		cin >> str;

		if (who[str] == 1)
			ret.push_back(str);
	}

	sort(ret.begin(), ret.end());
	cout << ret.size() << '\n';
	for (int i = 0; i < ret.size(); i++)
		cout << ret[i] << '\n';

	return 0;
}