[백준/C++] 1764 듣보잡

문제

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

입력

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

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

출력

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

---

접근법

처음의 접근법으로는 모든 요소를 돌아 해당 이름이 존재하는지 안하는지 확인하는 브루트포스를 사용하여 풀려고 하였다. N명의 이름을 배열이나 vector에 넣고, 다시 M명의 이름을 받을 때마다 배열에 해당 이름이 있으면 새로운 vector에 push, 없으면 넘어가는 식으로 구현을 하였다.

다음과 같이 시간초과가 나는 것을 확인할 수 있었다. 이에 순차탐색인 브루트포스 대신 이진탐색으로 같은 이름이 있는지 찾는 시간을 줄이고자 하였다.

---

코드

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

vector<string> v1;
vector<string> v2;

int main(){
    int N, M;
    cin >> N >> M;

    string temp;
    for(int i = 0; i < N; i++) {
        cin >> temp;
        v1.push_back(temp);
    }

    sort(v1.begin(), v1.end());


    for(int i = 0; i < M; i++) {
        cin >> temp;

        if(binary_search(v1.begin(), v1.end(), temp)) {
            v2.push_back(temp);
        }
    }

    sort(v2.begin(), v2.end());

    cout << v2.size() << endl;

    for(auto tmp : v2) {
        cout << tmp << endl;
    }

    return 0;
}

algorithm.h에서의 binary_search() 함수를 이용하여 vector내의 찾으려는 값이 있는지, 없는지를 시간복잡도 \(O(n)\)이 아닌 \(O(logn)\)으로 줄일 수 있다.

이진탐색은 탐색할 배열이나 vector가 정렬되어있어야한다. 꼭 binary_search() 전에 sort를 진행해야 한다.

---

원문: Velog