[set / 집합]

BOJ 2776 암기왕
주어진 수가 있는지 없는지 확인하는 자료구조가 필요하다.
대표적으로 원소의 존재성은 아래의 자료구조 중에서 선택한다.

1. 리스트를 정렬한 후 binary search(이분탐색)로 확인.
2. set(집합) 자료구조 이용.
3. hash(hash, map, dict) 자료구조 이용.

이 문제는 카운팅이 필요없으므로 2번이 좋겠다.
set은 고등학교때 배운 그 집합과 동일하다. 순서가 중요하지 않고 존재성만이 중요한 자료구조이다. 수학의 집합처럼 동일한 연산을 제공한다.

대표적인 set의 연산
1. 집합의 선언 - set() ({}로 선언하면 dict가 된다)
2. 원소의 삽입 : add, update
3. 원소의 삭제 : remove(없는 원소의 경우 KeyError 발생), discard
4. 합집합 : '|', A.union(B)
5. 교집합 : '&', A.intersection(B)
6. 차집합 : '-', A.difference(B)
7. 대칭차집합 : '^'
8. iterable하다. 중복된 원소 없음

시간복잡도 출처 링크

파이썬에서 set을 구현할때 아마도 dict와 유사하게 구현한 것 같다.
(그래서인가 set도 {}지만 s = {}으로 하면 set이 아니라 dict로 된다.)

참고로 C++의 set은 이진트리로 구현되어있어서 탐색이 $O(1)$이 아니라 $O(\log{n})$이다.

다시 문제로 들어와서... 수첩1인 set을 만들고 수첩2에서 각 원소마다 set에 존재하는지 확인만 하면 된다.

# Python code
T = int(input())
for _ in range(T):
    N = int(input())
    S = set(map(int, input().split()))
    M = int(input())
    L = list(map(int, input().split()))
    for x in L:
        if x in S:
            print("1")
        else:
            print("0")

진짜 파이썬의 위대함....

비슷한 문제를 풀어보자

유제1. 회사에 있는 사람
출근(enter)하면 add, 퇴근(leave)하면 remove연산을 해준다.
PYPY3의 경우, set은 오름차순으로 이미 정렬되도록 구현되어있다.

n = int(input())
S = set()
for _ in range(n):
    name, log = input().split()
    if log == 'enter':
        S.add(name)
    else:
        S.remove(name)
L = list(S)
L.sort(reverse = True)
for x in L:
    print(x)

유제2. 대칭차집합
A-B, B-A의 원소의 개수를 더하면된다. 합집합에서 교집합을 빼도 된다.
참고로 대칭차집합의 연산(A^B)을 기본적으로 제공한다.

n, m = map(int, input().split())
A = set(map(int, input().split()))
B = set(map(int, input().split()))
a = list(A.difference(B))
b = list(B.difference(A))
print(len(a) + len(b))
# print(len(A^B)) is also possible