[BOJ] 1764번 듣보잡 (C++)

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

1764번: 듣보잡

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m;
	cin >> n >> m;
	
	vector<string> v;
	vector<string> t;
	string s, k;
	for(int i = 0; i < n; i++){
		cin >> s;
		v.push_back(s);
	}
	
	sort(v.begin(), v.end());
	for(int i = 0; i < m; i++){
		cin >> k;
		if(binary_search(v.begin(), v.end(), k)) t.push_back(k);
	}
	
	cout << t.size() << '\n';
	sort(t.begin(), t.end());
	for(string r : t){
		cout << r << '\n';
	}
	
	return 0;
}

find 함수를 사용하면 시간 초과가 발생해서 binary_search 함수를 사용하였다. binary_search 함수는 이진 탐색을 사용하기 때문에 함수가 제대로 작동하기 위해서는 사용 전에 먼저 정렬을 해주어야 한다!!