[C/C++] 백준 #1822 차집합(집합)

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

 

Difference of Sets

 

집합자료는 해시를 사용하는 해시 집합과 이진트리를 이용한 이진트리 집합이 있습니다.

이 문제에 있어서는 어떤 집합 자료 구조를 사용하든지 크게 문제는 없습니다.

 

제 경우에는 이진트리 집합을 사용했습니다.

 

A 집합을 만든다음에, B에 속하는 원소가 A 집합에 있는 경우 삭제를 했습니다.  그러면 A집합에는 차집합이 남아있게 됩니다.

 

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

//------------------------------------------------
//    baekjoon #1822
//        - by Aubrey Choi
//        - created at 2019-08-19
//------------------------------------------------
#include <stdio.h>
#include <set>

int main()
{
    unsigned n, m, s;
    std::set<unsigned> set;
    scanf("%u%u",&n,&m);
    while(n--) { scanf("%u",&s); set.insert(s); }
    while(m--) { scanf("%u",&s); if(set.find(s)!=set.end()) set.erase(s); }
    printf("%lu\n", set.size());
    if(set.size())
    {
        for(auto &k : set) printf("%u ", k);
        putchar('\n');
    }
}