[Baekjoon] 1764: 듣보잡 - (C3, S4) std::unorderd_set

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

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

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

1764번: 듣보잡

 

처음 N개의 이름을 입력받은 후, M개의 이름을 입력 받을 때 이미 입력받은 이름일 경우 이를 저장하여 그 수와 명단을 출력하면 된다. 

 

이를 위해 초기에 초기 이름 명단(names)와 중복 명단(ans)를 모두 vector로 구현하였으나, vector은 동적 배열로 구현되어 삽입 및 탐색 연산이 오래 걸리는 문제가 있었다. 이로 인한 시간 초과 문제를 해결하기 위해 unordered_set 컨테이너를 사용하여 names를 구현했다. 

 

std::unordered_set은 해시테이블을 사용해 내부적으로 요소를 저장하여 삽입/삭제/탐색 연산이 빠르다(std::set은 이진 트리 사용). 평균적으로 O(1)의 시간복잡도를 가지며 최악의 경우  O(n)의 시간 복잡도를 가진다.

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    string name;
    cin >> N >> M;

    unordered_set<string> names;
    vector<string> ans;

    for (int i = 0; i < N; i++)
    {
        cin >> name;
        names.insert(name);
    }

    for (int j = 0; j < M; j++)
    {
        cin >> name;
        if (names.find(name) != names.end()) // 이미 이름이 존재하면
            ans.push_back(name);
        else
            names.insert(name);
    }

    sort(ans.begin(), ans.end()); // 사전순 오름차순 정렬
    int size = ans.size();

    cout << size << '\n';
    for (int k = 0; k < size; k++)
        cout << ans[k] << '\n';

    return 0;
}

위와 같은 코드로 문제를 해결하였다. 

 

vector 사용

 

그런데, ans 역시 set을 사용한다면 더 빠르게 풀 수 있지 않을까? set은 내부적으로 정렬된 상태를 유지하기 때문에 sort 함수의 호출이 필요없다. 다만 vector의 push_back은 평균적으로 O(1)의 시간 복잡도를 가지는데 반해 set의 insert는 O(log n)의 시간복잡도를 가진다. sort함수는 O(nlogn)의 시간 복잡도를 가지므로, vector + sort 방식과 set 방식은 다음과 같이 계산된다.

 

vector + sort :

n번의 입력 -> n * O(1) = O(n) 

정렬 -> O(nlogn)

합 : O(n + nlogn) = O(nlogn)

 

set:

n번의 입력 -> n * O(logn) = O(nlogn)

 

따라서 두 방식 모두 이론적 시간 복잡도는 O(nlogn)이므로 비슷한 속도를 보일 것이다. 

#include <iostream>
#include <set>
#include <unordered_set>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    string name;
    cin >> N >> M;

    unordered_set<string> names;
    set<string> ans;

    for (int i = 0; i < N; i++)
    {
        cin >> name;
        names.insert(name);
    }

    for (int j = 0; j < M; j++)
    {
        cin >> name;
        if (names.find(name) != names.end()) // 이미 이름이 존재하면
            ans.insert(name);
        else
            names.insert(name);
    }

    int size = ans.size();

    cout << size << '\n';
    for (auto &s : ans)
        cout << s << '\n';

    return 0;
}

set 사용

확인 결과, set을 사용한 것이 4ms 더 빠른 것을 볼 수 있다. 근소한 차이로, 이는 입력의 크기나 환경에 따라 달라질 수 있으므로 이론적으로 동일한 성능이라고 봐도 될 듯 싶다.