BOJ - 1764. 듣보잡

문제

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

입력

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

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

출력

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

예제 입력 1

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1

2
baesangwook
ohhenrie

---

사용할 자료구조

• 중복되는 이름이 없다고 문제에서 언급했기 때문에 set이나 map을 떠올렸습니다. 그러나, key-value값으로 이루어진 자료구조는 필요없기 때문에 set을 사용하였습니다.

풀이 과정

1) 듣도 못한 사람과 보도 못한 사람 중 둘 다 해당되는 사람을 찾아야 한다. (두 집합의 교집합)

2) 먼저 듣도 못한 사람들을 입력받으면서 <듣못set>안에 담아둡니다.

3) 보도 못한 사람들을 입력받을 때마다 set안에 존재하는지를 검사해줍니다.

3-1) 만약 존재하면 또 다른 <듣보못set>에 넣어줍니다.

for(int i=0;i<m;i++){
        string name;
        cin>>name;
        if(deutdo.find(name)!=deutdo.end()){ //name이 있는지 찾는 검사
            deutbodo.insert(name);
        }
    }

4) set의 크기를 먼저 출력해주고, set안에 있는 이름들을 순차적으로 출력해주면 됩니다.

(set은 기본적으로 오름차순으로 정렬되어있기 때문에 따로 정렬작업을 수행하지 않아도 됩니다.)

cout<<deutbodo.size()<<'\n';
for(auto i=deutbodo.begin();i!=deutbodo.end();i++){
        cout<<*i<<'\n';
    }

시간 복잡도

map은 삽입 연산을 하는데 O(logN)만큼 걸린다

n만큼 루프를 돌며 삽입연산을 하고 m만큼 루프를 돌며 삽입 연산을 하기 때문에 시간복잡도는 O(NlogN)입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <functional>
using namespace std;

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    set<string> deutdo;
    set<string> deutbodo;
    for(int i=0;i<n;i++){
        string name;
        cin>>name;
        deutdo.insert(name);
    }
    for(int i=0;i<m;i++){
        string name;
        cin>>name;
        if(deutdo.find(name)!=deutdo.end()){
            deutbodo.insert(name);
        }
    }
    cout<<deutbodo.size()<<'\n';
    for(auto i=deutbodo.begin();i!=deutbodo.end();i++){
        cout<<*i<<'\n';
    }

    return 0;
}