백준 / BOJ / 1764 듣보잡 C++

www.acmicpc.net/problem/1764

1764번: 듣보잡

거친 제목의 문제 이름에 이끌려 들어가보았지만, 쉬운 문제였습니다. (그렇지만 틀렸었다.)

듣도 못한 사람을 listen 벡터에 넣었습니다. 

 

처음에는 listen 벡터 외에 see 벡터를 추가하여 보도 못한 사람들의 벡터를 만들어 이분 탐색을 진행하였지만, 시간 초과가 났습니다. (시간 초과가 이것 때문은 아니고, 처음에는 이분 탐색 알고리즘을 직접 구현했었지만, 시간초과나서 그냥 algorithm 라이브러리에 있는 binary_search를 이용하였습니다.)

 

문제는 간단합니다. 그냥 둘 다 공통으로 있는 사람을 찾으면 됩니다. 너무 간단한 문제라 쓸 말이 없습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std; 

int n, m;
vector<string>listen;
vector<string>result;

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

	listen.resize(n);
	for (int i = 0; i < n; i++)
		cin >> listen[i];

	sort(listen.begin(), listen.end());

	for (int i = 0; i < m; i++)
	{
		string s2;
		cin >> s2;
		bool check = binary_search(listen.begin(), listen.end(), s2);
		if (check)
			result.push_back(s2);
	}

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