[BOJ/백준 1764][C++] 듣보잡

문제

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

 

문제 내용

듣도 못한 사람 수 n명, 보도 못한 사람 수 m명의 이름이 주어진다.

두 명단에 공통으로 들어있는 사람의 수와 명단을 출력하면 된다.

 

문제 풀이

이 문제에서 find() 함수를 써서 하면 시간 초과가 난다.
n, m의 범위가 모두 500,000 이하의 자연수이기 때문이다.

그렇기 때문에 binary_search()를 사용했다.
binary_search()는 정렬된 상태에서 사용 가능하다.

그래서 듣도 못한 사람들의 명단을 sort()한 뒤에 보도 못한 사람이 포함되었는지 binary_search()를 사용해서 확인한다.
만약 듣도 보도 못한 사람이라면 result 벡터에 추가하고 나중에 결과 출력할 때 출력하면 된다.

 

코드

#include <iostream>
#include <algorithm> //binary_search() : 정렬된 상태에서 사용
#include <vector>
using namespace std;

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

	//입력
	int n, m;
	cin >> n >> m;
	vector<string>v1(n); //듣도 못한 사람
	vector<string>result;
	for (int i = 0; i < n; i++) cin >> v1[i];
	
	//문제 해결
	sort(v1.begin(), v1.end());

	string mm;
	for (int i = 0; i < m; i++) {
		cin >> mm; //보도 못한 사람
		if (binary_search(v1.begin(), v1.end(), mm)) result.push_back(mm);

	}
	sort(result.begin(), result.end());

	//결과 출력
	cout << result.size() << '\n';
	for (string tmp : result) cout << tmp << '\n';
}