[BOJ] 백준 1764 듣보잡 c++ (문자열, map, unordered_map)

문제 출처 : https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 

풀이

브루스포스로 해결하면 시간 초과가 발생한다.

 

map을 이용해서 듣도 못한 사람을 저장하고, 보도 못한 사람을 해당 map에서 찾아 있는 경우 vector에 추가 해주었다.

sort 함수를 사용해 사전순으로 출력하였다. (sort를 사용하려면 algorithm 헤더 파일을 선언해주어야 한다!)

 

이분탐색(binary_search)을 활용해 겹치는 사람을 찾는 방법도 있다. 아래 코드는 map 코드이다!

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

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

	map<string, int> m;
	vector<string> v;

	int N, M;
	cin >> N >> M;

	int cnt = 0;
	string str = "";
	while(N--){
		cin >> str;
		m.insert({str, 1}); // m[str] = 1; 도 가능
	}

	while(M--){
		cin >> str;
		if(m[str] == 1){
			v.push_back(str);
			cnt++;
		}
	}
	
	sort(v.begin(), v.end());

	cout << cnt << '\n';
	for(auto elem : v) cout << elem << '\n';

	return 0;
}

unordered_map을 활용한 풀이

#include <bits/stdc++.h>

using namespace std;

int N, M;

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

	unordered_map<string, int> um;
	vector<string> ans;

	cin >> N >> M;
	string str = "";
	for(int i = 0; i < N; i++) {
		cin >> str;
		um[str] = 1;
	}
	for(int i = 0; i < M; i++) {
		cin >> str;
		if(um.find(str) != um.end())
			ans.push_back(str);
	}
	sort(ans.begin(), ans.end());

	cout << ans.size() << '\n';
	for(auto elem : ans)
		cout << elem << '\n';
	return 0;
}