문제

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

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

예제

---

풀이과정

완전 탐색: O(nm)

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

int main() {
	// 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M 
	// 듣도 && 보도 못한 사람의 수와 명단 구하기 

	// N, M은 500,000 이하의 자연수 
	int n, m;
	cin >> n >> m;

	vector<string> v1;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		v1.push_back(s);
	}

	vector<string> v2;
	for(int i = 0; i < m; i++){
		string s;
		cin >> s;
		v2.push_back(s);
	}

	// v1과 v2에서 중복해서 등장하는 사람들의 수와 이름을 구한다!
	int count = 0; 
	vector<string> v3;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(v1[i] == v2[j]){
				count++;
				v3.push_back(v1[i]);
			}
		}
	} // 시간 복잡도: O(nm) 

	// 사전 순으로 정렬 
	sort(v3.begin(), v3.end()); // O(NlogN) 

	cout << count << endl;
	for(auto e: v3){
		cout << e << endl;
	}
	
	return 0;
}

더 효율적인 방법 고민하기

https://ongveloper.tistory.com/112

map 이용: O(n + m)

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

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	int n, m;
	cin >> n >> m;

	// 전부 맵으로 입력을 받는데, 
	// 하나의 key에 대한 value가 2이상이면 이름이 중복된 것! 
	map<string, int> map;
	vector<string> v; // 중복되는 이름 저장 

	for(int i = 0; i < n + m; i++){
		string s;
		cin >> s;
		map[s] += 1;

		if(map[s] > 1){ // 이름이 2번 이상 등장하면 
			v.push_back(s); 
		}
	}
	
	// 사전 순으로 정렬 
	sort(v.begin(), v.end());
	
	cout << v.size() << endl;
	for(auto e: v){
		cout << e << endl;
	}
	
	return 0;
}

이진 탐색: O(m * logn)

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

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	vector<string> v1, v2;
	string s;

	for(int i = 0; i < n; i++){
		cin >> s;
		v1.push_back(s);
	}
	
	// 사전 순으로 정렬 
	sort(v1.begin(), v1.end()); 

	// 이진 탐색으로 중복되는 이름 탐색하기!  
	for(int i = 0; i < m; i++){
		cin >> s;
		if(binary_search(v1.begin(), v1.end(), s)){
			v2.push_back(s);
		}
	}
	
	// 사전 순으로 정렬 
	sort(v2.begin(), v2.end()); 
	
	cout << v2.size() << endl;
	for(auto e: v2){
		cout << e << endl;
	}
	
	return 0;
}