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

문제

문제 분석

- 중복과 관련된 것은 set/map 해시 알고리즘을 사용하면 유용하다.

- 듣도이면서 보도인 사람인 듣보잡의 수를 구해야 하므로 듣도에서 set에 insert을 하고, 보도에서 set에 들어있는지 (듣도인 사람인지) 체크해서 주어진대로 출력하면 풀 수 있는 문제이다.

- 듣보잡인 사람의 이름을 사전순으로 나열해야 하므로 vector(가변 배열)을 하나 더 만들어 듣보잡인 사람을 담고, 정렬을 하면 된다.

정답 코드

- 특히 set/map 자료구조에서 해당 key 값이 있는지 판단을 하기 위해서는 s.find()가 s.end()와 같은지 판단하면 된다. s.end()까지 갔다는 것은 해당 key 값이 없다는 것이기 때문에 s.end()이 되는 것이다.

// 풀이 시간 : 11분 52초
// 듣도에서 set에 insert하고, 보도에서 set에 담겨있는지 확인해서 담겨있으면 듣보잡의 수를 하나 더하고, 명단에 추가한다.

#include <iostream>
#include <unordered_set> // key값이 정렬될 필요 x
#include <vector>
#include <algorithm>

using namespace std;

unordered_set<string> s;
vector<string> v; // 듣보잡인 사람 이름 모음

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int N, M;
	cin >> N >> M;
	// 듣도 입력
	for (int i = 0; i < N; i++) {
		string name;
		cin >> name;
		s.insert(name);
	}

	// 보도 입력
	int ans = 0; // 듣보잡 사람 수 
	for (int i = 0; i < M; i++) {
		string name;
		cin >> name;
		if (s.find(name) != s.end()) { // 듣도에 있는 경우
			ans++;
			v.push_back(name);
		}
	}

	sort(v.begin(), v.end()); // 오름차순 정렬
	// 정답 출력
	cout << ans << "\n";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << "\n";
	}

	return 0;
}