문제풀이/백준

[C++] 백준 1764번 문제풀이

Viper1 2021. 2. 11. 19:48

이 문제를 풀 때 들었던 생각은

듣도 못한 사람을 vector 에 넣고

보도 못한 사람이 듣도 못한 사람의 vector 안에 있다면 듣보잡의 vector안에 넣어야 겠다고 생각했다.

보도 못한 사람이 듣도 못한 사람의 vector 안에 있는가를 알기 위해선

탐색을 해야하는데 시간이 많이 걸리기 때문에 

binary search 를 이용하여 풀었다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int N, M;
	cin >> N >> M;
	vector<string>db;
	vector<string>dbj;
	while (N--) {
		string name;
		cin >> name;
		db.push_back(name);
	}
	sort(db.begin(), db.end());
	while (M--) {
		string name;
		cin >> name;
		if (binary_search(db.begin(), db.end(), name)) {
			dbj.push_back(name);
		}
	}
	sort(dbj.begin(), dbj.end());
	cout << dbj.size() << "\n";
	for (auto x : dbj)
		cout << x << "\n";
	return 0;
}