[백준 #1764] 듣보잡 (C++)

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

1764번: 듣보잡

이 문제는 벡터와 이진 탐색을 통해 풀었다.

 

듣도 못한 사람의 명단을 벡터(v)에 저장한 후, 이진 탐색을 하기 위해 정렬하고

보도 못한 사람의 이름(s)을 입력받으면서

해당 이름이 벡터 v에 있는지 확인하기 위해 이진 탐색을 사용했다.

binary_search(v.begin(), v.end(), s)

 

이진 탐색 STL은 해당 값이 존재하면 1을 리턴하므로

만약 보도 못한 사람의 이름(s)이 벡터 v에 있다면,

결괏값 벡터에 push_back을 해주었다.

 

그다음 사전 순으로 출력하기 위해 결괏값 벡터를 오름차순으로 정렬해주었다.

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;	// n: 듣도 못한 사람의 수, m: 보도 못한 사람의 수
	cin >> n >> m;
	string s;

	vector<string> v(n);	// 사이즈가 n인 벡터 생성
	vector<string> result;	// 결괏값 담을 벡터 생성

	for (int i = 0; i < n; i++) {
		cin >> v[i];	// 듣도 못한 사람의 명단을 벡터에 입력
	}

	sort(v.begin(), v.end());	// 이진 탐색을 위해 정렬

	for (int i = 0; i < m; i++) {
		cin >> s;	// 보도 못한 사람 명단 입력

		// 이진 탐색을 통해 s가 벡터 v에 있으면 결괏값 벡터에 넣기
		if (binary_search(v.begin(), v.end(), s)) {
			result.push_back(s);
		}
	}
    
	sort(result.begin(), result.end());	// 사전순 출력을 위해 오름차순 정렬
	cout << result.size() << "\n";
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

	return 0;
}