BOJ 1764 듣보잡 / C++

문제 링크 : https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 

풀이

n개의 문자열과 m개의 문자열을 입력받아 같은 문자열을 출력해주는 코드를 짜면 된다.

처음에는 2중 for문을 사용하는 풀이를 사용했지만 시간 초과가 나서 binary search를 이용하여 다시 풀었다.

참고로, binary search를 사용하기 위해선 정렬이 필요하다.

 

이중 for문 코드(시간 초과)

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);

	int n, m, cnt = 0;
	cin >> n >> m;
	vector<string> names1;
	vector<string> names2;
	vector<string> ans;

	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		names1.push_back(tmp);
	}

	for (int i = 0; i < m; i++) {
		string tmp;
		cin >> tmp;
		names2.push_back(tmp);
	}

	for (vector<string>::iterator it1 = names1.begin(); it1 != names1.end(); ++it1) {
		for (vector<string>::iterator it2 = names2.begin(); it2 != names2.end(); ++it2) {
			if (*it1 == *it2) {
				cnt++;
				ans.push_back(*it1);
			}
		}
	}

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

binary search 코드

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);

	int n, m, cnt = 0;
	cin >> n >> m;
	vector<string> names;
	vector<string> ans;

	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		names.push_back(tmp);
	}
	sort(names.begin(), names.end());

	for (int i = 0; i < m; i++) {
		string tmp;
		cin >> tmp;
		if (binary_search(names.begin(), names.end(), tmp)) {
			cnt++;
			ans.push_back(tmp);
		}
	}

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