[C/C++] 백준 #1764 듣보잡(집합자료)

이번 문제는 집합 자료를 사용하면 쉽게 풀리는 문제입니다.

 

off brands

 

문제는 들어본 적이 없는 사람들의 리스트와 본적 없는 사람들의 리스트가 주어졌을 때, 듣보잡(들어보지도, 본적도 없는) 리스트를 구하는 것입니다.  그런데, 최종 리스트는 사전순으로 배열해야 합니다.

 

가장 간단한 방법을 두 집합을 만들고, 그 집합의 교집합을 구하는 방법이겠죠.  정렬된 리스트를 만들고 교집합을 만들면 알고리즘 효율은 \(O(N \log N + M \log M)\)이 됩니다.  정렬하는데 필요한 부분입니다.  정렬한 두개의 리스트에서 교집합 내용을 찾는 것은 \(O(N+M)\)이 되겠죠.

 

저는 두개의 집합을 이용했습니다.  첫번째는 해시집합이고, 두번째는 정렬집합입니다.  해시집합은 정렬되지는 않았지만, 삽입, 검색이 모두 \(O(1)\)인 효율을 가지고 있습니다.  정렬 집합은  \( O(\log N) \)이고요.

 

처음 들어보지 못한 집합을 만들 때에는 해시집합을 이용했습니다.  해시집합을 만드는 알고리즘 효율은 \(O(N)\)이 됩니다.  다음은 M개의 본적 없는 사람들의 리스트에 대해 해시집합에서 검색을 해서 존재하는 경우 정렬 집합에 넣었습니다.  최악의 경우 \(O(M \log M)\)이 됩니다.  그래서 \(O(N + M \log M)\)의 알고리즘 효율이 됩니다.  그렇게까지 좋은 알고리즘 효율은 아닙니다.  조금 더 개선을 하고자 한다면, N, M 중 대소 비교를 해서 적은쪽을 이용해서 정렬 집합을 넣는 방법이 있겠지만, 사실상 얻어지는 이득이 크지는 않을겁니다.  실제 정렬에 들어갈 리스트의 개수는 N, M중 작은 값으로 유계를 가지니까요.

 

집합 자료 구조는 해시 집합(unordered set)과 정렬 집합(ordered set)이 있다는 점을 알면 좋을 듯 합니다.  해시 집합이 \(O(1)\)의 삽입, 삭제, 탐색의 효율을 가지고 있다고 하지만, 결코  \(O(\log N)\)의 효율을 가지는 정렬 집합보다 좋은 것은 아닙니다.  둘 다 비슷한 정도의 효율을 가지고, 때로는 정렬 집합이 더 우수하니까요.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//-----------------------------------------------
//    baekjoon #1764
//        - by Aubrey Choi
//        - created at 2019-10-09
//-----------------------------------------------
#include <stdio.h>
#include <unordered_set>
#include <set>
#include <string>

int main()
{
    std::unordered_set<std::string> s1;
    std::set<std::string> s2;
    int n, m;
    char name[24];
    scanf("%d%d",&n,&m);
    while(n--) { scanf("%s", name); s1.insert(name); }
    while(m--) { scanf("%s", name); if(s1.find(name)!=s1.end()) s2.insert(name); }
    printf("%lu\n", s2.size());
    for(auto k : s2) printf("%s\n", k.c_str());
}