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

처음엔 

듣도 못한 사람 벡터 하나, 보도 못한 사람 벡터 하나, 그리고 듣보잡 벡터 하나 이렇게 벡터 3개를 사용하려 하였다.

 

하지만 이진탐색 트리를 사용하여 좀더 효율적으로 할수 있다는 것을 알게 된후 다시 코딩 하였다.

 

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

int M, N;
vector<string> v;

bool binarySearch(int low, int high, string name) {
	if (low > high)
		return false;
	else {
		int mid = (low + high) / 2;
		if (!v[mid].compare(name))
			return true;
		else if (v[mid] > name)
			return binarySearch(low, mid - 1, name);
		else 
			return binarySearch(mid + 1, high, name);
	}
}

int main(void){
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		string name;
		cin >> name;
		v.push_back(name);
	}
	sort(v.begin(), v.end());

	vector<string> result;
	for (int i = 0; i < M; i++) {
		string name;
		cin >> name;
		if (binarySearch(0, v.size(), name))
			result.push_back(name);
	}
	
	sort(result.begin(), result.end());
	
	cout << result.size() << endl;
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << endl;
	}
	return 0;
}