BOJ 1764 C++

문제접근

정렬후 이분탐색

코드

#include <bits/stdc++.h> 
#define ll long long

using namespace std;


int ebun(string &target,vector<string> &x)
{
	int lo = 0;
	int hi = x.size() - 1;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (x[mid] < target)
			lo = mid + 1;
		else if (x[mid] > target)
			hi = mid - 1;
		else
			return 1;
	}
	return 0;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m; cin >> n >> m;
	vector<string> d(n);
	for (int i = 0; i < n; i++)
		cin >> d[i];
	sort(d.begin(), d.end());
	string tmp;
	vector<string> ans;
	for (int i = 0; i < m; i++)
	{
		cin >> tmp;
		if (ebun(tmp,d))
			ans.push_back(tmp);
	}
	sort(ans.begin(), ans.end());
	int size = ans.size();
	cout << size << "\n";
	for (int i = 0; i < size; i++)
		cout << ans[i] << "\n";
	return 0;
}