2022.02.26 [백준] (python 파이썬) 집합

 

https://www.acmicpc.net/problem/11723

11723번: 집합

---

풀이

처음 코드를 작성 할때 set을 이용했다. 이유는 포함유무 체크와 추가 제거의 시간복잡도가 O(1)이기 때문이다.

하지만 set을 써도 시간초과가 발생했다.

그래서 더 시간을 줄일 방법이 있을까 생각했다. 그러다 문제에서 x의 범위가 1~20인것을 보고 범위가 좁으니 비트마스킹을 이용해도 되겠다는 생각이 들었다.

그래서 check을 False로 길이가 21인 배열을 만들었다. 이유는 각 숫자와 인덱스를 맞추기 위해 앞에 0을 추가했다.

그리고 각 조건이 주어질때마다 배열에 수를 저장하지 않고 비트마스킹을 이용해 들어있으면 True, 비어있으면 False로 표시하면서 문제를 해결했다.

import sys
input=sys.stdin.readline
 
check=[False]*21
 
for _ in range(int(input())):
    s=list(input().split())
    if s[0]=='add':
        if not check[int(s[1])]:
            check[int(s[1])]=True
        else:
            continue
    elif s[0]=='remove':
        if check[int(s[1])]:
            check[int(s[1])]=False
        else:
            continue
    elif s[0]=='check':
        if check[int(s[1])]:
            print(1)
        else:
            print(0)
    elif s[0]=='toggle':
        if check[int(s[1])]:
            check[int(s[1])]=False
        else:
            check[int(s[1])] = True
    elif s[0]=='all':
        check=[True]*21
    elif s[0]=='empty':
        check=[False]*21