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

https://www.acmicpc.net/problem/1764

시간초과를 잘 처리해야 하는 문제이다.

---

#include <iostream>
#include <set>

using namespace std;

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);

	int N, M;
	set <string> list;
	set <string> ans;

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		string temp;
		cin >> temp;

		list.insert(temp);
	}

	for (int i = 0; i < M; i++)
	{
		string temp;
		cin >> temp;

		auto check = list.find(temp);
		if (check != list.end())
			ans.insert(temp);
	}

	cout << ans.size() << '\n';
	for (string str : ans)
		cout << str << '\n';

	return 0;
}

시간초과를 방지하기 위해 tie와 sync_with_stdio를 사용하였다.

vector대신 자동으로 정렬해주는 set을 사용하였고 값을 찾을 때에는 find()함수를 사용하였다. 

이 때 기본 std:find() 같은 경우 시간복잡도 O(N)이지만, set에 있는 find를 사용할 경우 O(logN)으로 줄어들기 때문에 이를 잘 알고 find를 사용해야 한다.