문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, ..., 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다.

입출력

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

입출력 예시

---

해설

배열을 사용하여 '구현'의 개념으로 접근하면 훨씬 짧은 코드로 작성하고 더 빠르게 실행시킬 수 있지만

비트마스크를 사용하여 집합을 표현할 수 있다.

• 집합 S에 i 추가
  => S | ( 1 << i)
• i 검사
  => S & ( 1 << i )
• i 제거
  => S & ~( 1 << i )
• i 를 0에서 1로, 1에서 0으로 바꾸기
  => S ^ ( 1<< i )
• 전체 집합으로
  => ( 1<<N ) - 1
• 공집합으로
  => S = 0

코드

# 백준 11723 집합 실버5 / 비트마스킹
import sys

# 수행 연산 수
M = int(sys.stdin.readline())

#공집합 S
S = 0

for i in range(0, M):
    # 명령어 입력
    command = sys.stdin.readline()
    
    # all, empty 명령어때문에 추가한 부분임. 뒤에 숫자가 없으니 오류를 일으켜서 추가함
    # 입력된 명령어 숫자와 커맨드로 나누기
    if len(command.split()) >1:
        num = int(command.split()[1])-1 # x는 1이하 20이지만 이진수에서는 0의자리~19의자리로 나타내야 하므로 -1
    command = command.split()[0]

    # 명령 수행
    # add : S에 x 추가하기. 있으면 무시
    if command == "add" :
        S= S | (1<<num)
    # remove : S에서 X 제거하기. 없으면 무시
    elif command == "remove":
        S = S & ~(1<<num)
    # check : S에 X가 있으면 1, 없으면 0 출력
    elif command == "check" :
        print("1" if S & (1<<num) else "0")
    # toggle : S에 X가 있으면 제거하고 없으면 추가하기
    elif command == "toggle" : 
        S = S ^ (1<<num)
    # all : 전체집합으로 만들기
    elif command == "all" : 
        S = (1<<20)-1
    # empty : 공집합으로 만들기
    elif command == "empty" : 
        S = 0

---

생각

비트마스킹이 더 오래걸림 ^^;;;
그냥 비트마스킹을 알아가는 차원이라고 생각하자..