[백준] 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

 

소스코드

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

string listen[500001], see[500001];

int binary_search(int low, int high, int num) {	//이진탐색을 통해 listen 배열에 있는 사람이 see 배열에도 있는지 확인한다.
    if(low>high) return -1;	//존재하지 않으면 -1을 리턴한다.
    else {
        int mid=(low+high)/2;
        if(listen[num]==see[mid]) return mid;	//존재하면 해당 인덱스 값을 리턴한다.
        else if(listen[num]<see[mid]) return binary_search(low, mid-1, num);
        else return binary_search(mid+1, high, num);
    }
}

int main() {
    int n, m, cnt=0;
    int result[500001];
    
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>listen[i];
    for(int i=0;i<m;i++) cin>>see[i];
    sort(listen, listen+n);	//listen 배열을 정렬한다.
    sort(see, see+m);	//see 배열을 정렬한다.
    
    for(int i=0;i<n;i++) {
        if(binary_search(0, m, i)!=-1) result[cnt++]=binary_search(0, m, i);	//이진탐색을 통해 찾은 듣보잡 명단을 result에 저장한다.
    }
    cout<<cnt<<endl;	//듣보잡 수를 출력한다.
    for(int i=0;i<cnt;i++) {
        if(result[i]!=-1) cout<<see[result[i]]<<endl;	//듣보잡 명단을 사전순으로 출력한다.
    }
    return 0;
}

두 배열 간에 동일한 값을 탐색하는 방법으로 이진 탐색을 이용하여 시간 복잡도를 줄이고자 하였습니다.