백준 11723 파이썬

11723번: 집합

Baekjoon Online Judge스타트링크 (Startlink)

11723번 : 집합
알고리즘: 비트마스크

해설

해당 문제는 최대 3백만 번의 연산을 요구하는 만큼 효율적인 연산 · 메모리 사용이
필요하다.

비트마스크란(Bitmask)?
정수의 각 비트를 bool 자료형처럼 사용하여 정수 자료형을 마치 여러개의 bool로
이루어진 배열처럼 사용하는 방법이다.
일반적인 4byte int로 2^32가지 경우의 수를 표현 할 만큼 메모리 효율성이 좋다.

2진수 n자리 수를 문제의 x에 대응하면 집합S를 0b000000000000000000000로 나타낼 수 있다.
예) 집합S에 2, 5, 9, 15, 20이 들어있는경우 S = 0b100001000000000100100

아래 예시들은 편의를 위해 1 <= X <= 10으로 가정하겠다

Add X
1을 << X 한 후 S와 OR 연산한다.
예) S ={ 2, 5 } / Add 7

Remove X
1을 << X 한 후 ~(not) 연산하여 S와 AND 연산한다.
예) S = { 2, 5, 7 } / Remove 7

Toggle X
1을 << X 한 후 S와 XOR 연산한다.
예) S = { 2, 5, 7 } / Toggle 7

Empty X
모든 비트가 0 이므로 S = 0

All
( 1 << X_MAX + 1 ) - 1

Check
1을 << X 한 후 AND연산 결과가 0이면 없음, 0이 아니라면 있음
예) S = { 2, 5, 7 } / Check 7

예) S = { 2, 5 } / Check 7

코드

import sys

m = int(sys.stdin.readline())
s = 0b000000000000000000000

for i in range(m):
    arr = sys.stdin.readline().split()
    calc = arr[0]

    if calc == 'all':
        s = (1 << 21) - 1
    elif calc == 'empty':
        s = 0
    elif calc == 'add':
        s |= 1 << int(arr[1])
    elif calc == 'remove':
        s &= ~(1 << int(arr[1]))
    elif calc == 'toggle':
        s ^= (1 << int(arr[1]))
    elif calc == 'check':
        print(1 if (s & (1 << int(arr[1]))) != 0 else 0)