[개쉬운 풀이] 백준 1764 듣보잡

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

문제

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

입력

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

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

---

생각

1. 듣도 못한 사람과 보도 못한 사람의 합집합을 구하는 문제이다. 따라서 듣도 못한 사람을 먼저 Container에 담아두고, 보도 못한 사람들을 키 값으로 주었을 때 존재하는지 판단한다.
2. 합집합, 존재의 유무만을 판단하면 되므로 set을 사용하였다.
3. vector에 answer를 담고 사전순으로 출력해야 하므로 sort()함수를 이용한다.

풀이

1. set을 선언하고 듣도 못한 사람의 명단을 모두 set에 insert한다.
2. find()함수를 통해 보도 못한 사람의 명단이 set안에 있는 지 확인한다.
3. 존재한다면 vector에 담는다.
4. 이후 사전순으로 출력을 해야하므로 bool cmp()를 만들고 이를 이용하여 sort()한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#define endl '\n'
using namespace std;

// 사전순으로 출력하기 위함, 역순은 A > B
bool cmp (string A, string B){
    return A < B;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    set<string> s;
    vector<string> list;

	//set에 듣도 못한 사람을 담는다.
    for(int i = 0; i < n; i++){
        string x;
        cin >> x;
        s.insert(x);
    }

	//set에 담긴 보도 못한 사람을 찾는다.
    for(int i = 0; i < m; i++){
        string x;
        cin >> x;

		//찾으면 vector에 담는다.
        if(s.find(x) != s.end()){
            list.push_back(x);
        }
    }

	//사전순으로 정렬한다.
    sort(list.begin(), list.end(), cmp);
    cout << list.size() << endl;
    for(auto s : list){
        cout << s << endl;
    }

    return 0;
}