<백준 알고리즘> 1764번 듣보잡

듣보잡 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	6625	2540	1799	39.925%

문제

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

입력

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

출력

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

예제 입력 1 

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1 

2
baesangwook
ohhenrie

<풀이과정>

어렵지 않은 문제인데 생각지도 못한 곳에서 실수를 하는 바람에 의외로 고생을 좀 했다.

기본 아이디어는 듣지못한 사람들을 입력받아 배열로 만들고 보도 못한 사람들을 한명씩 입력하고 듣도못한 사람들 배열에서 있는지 확인하는 방식이다. 

여기서 빠르게 배열을 탐색하기 위해 이분탐색함수 binary_search를 사용했는데  이분탐색 알고리즘은 찾을 사전역할을 하는 것을 반드시 정렬된 상태로 만들어주고 해줘야 한다는 것을 잊었다!

중복되는 것을 찾았으면 새로운 배열에 넣고 정렬 한 후 출력해주면 된다. 

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
 
int main(){
    int N,M;
    cin >> N >> M;
    
    vector<string> v1(N);// 듣도못한 
     vector<string> l2;// 듣보잡  
    
    for(int i=0;i<N;i++){// 듣도못한 배열에 넣기 
        cin >> v1[i];
        //v1.push_back(a);
    } // 확인완료 잘들어갔음 
    sort(v1.begin(),v1.end()); //<-- 이분탐색은 반드시 정렬된 사전을 가지고 해야 의미가 있다.  
    string b;
 
    while(M--){// 보도못한 
        cin >> b;
        
        if(binary_search(v1.begin(),v1.end(),b)){
            l2.push_back(b);// 듣보잡에 넣는다
        }
    }
    sort(l2.begin(),l2.end());
    cout << l2.size() << "\n";
    
    for (auto x:l2){
        cout << x << "\n";
    }
 
    return 0;
}