[백준11723번] 집합 / Python3

문제

비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.

예제 입력 1

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0

나의 풀이

비트마스크를 사용해서 푸는 문제이다. 비트마스크란 쉽게말하면 각 자리의 비트를 이용해 bool형 list를 만드는 것으로 볼 수 있다. 예를들어 0부터 5까지의 bool리스트를 만들면 [True, False, False, False, True]라면 비트마스크를 사용하면 10001처럼 자리수에 따라 True나 False에 대한 정보를 담을 수 있는 것이다. 리스트에서는 인덱스를 사용해 [1]처럼 각 원소에 접근하지만 비트마스크를 사용한다면 비트연산자인 쉬프트 연산자를 사용하여 접근할 수 있다. 1 << 1과 같이 1을 왼쪽으로 쉬프트하면 10이 된다. 그리고 &, |, ^, ~와 같은 연산자들을 사용해 각 원소의 값을 변경하거나 확인을 할 수 있다. 비트마스크를 사용하면 list를 사용하는 것에 비해 메모리를 절약할 수 있다는 장점이 있다. 따라서 이 문제는 메모리 제한이 아주 낮아 비트마스크를 사용하여 풀 수 있었다.

그럼 이 문제에서 각 연산들에 대하여 비트연산을 어떻게 사용해야 되는지를 살펴보겠다. (이 예에서는 비트가 1이면 원소가 있고 0이면 없는 것으로 생각하겠다. 그리고 4비트를 예로들겠다.)

• add x : add의 경우 x자리의 값을 1로 바꾸면 된다. 따라서 |연산을 사용하면 있어도 1, 없어도 1의 값이 된다는 것을 활용하면된다. 예를들면, 0000 | (1 << 2) = 0100, 0100 | (1 << 2) = 0100이 된다.
• remove x : remove의 경우 add와 반대로 x자리의 값을 0으로 바꾸면 된다. 따라서 쉬프트 연산으로 해당자리까지 이동한 후 ~연산자를 통해 비트를 반전시키고 &연산을 거쳐주면 된다. 예를들면, 0110 & ~(1 << 2) = 0110 & 1011 = 0010 이 된다. 즉, 각자리의 비트들을 반전시켜줌으로 x자리의 비트를 제외하고는 모두 1과 &연산을 하므로 그대로 유지가 되는 것이다.
• check x : check는 쉬프트 연산으로 이동 후 &을 통해 0인지 0이 아닌지를 확인하면 된다. 0이라면 x자리의 비트가 0이라는 뜻이고, 결과값이 0이 아니라면 x자리의 비트가 1이라는 뜻이기 때문이다.
• toggle x : toggle은 해당 비트의 값을 반전시켜주면 된다. xor연산인 ^를 사용하면 된다. xor은 0 ^ 1 = 1, 1 ^ 1 = 0이므로 반전이 되는 것을 확인할 수 있다. 따라서 예를들면, 0100 ^ (1 << 2) = 0000이 된다.
• all : all은 모든 비트를 1로 바꾸면 된다. 4비트를 모두 1로 만들기 위해서는 5번의 left shift한 값에서 1을 빼면 된다. 즉, (1 << 5) - 1 = 10000 - 00001 = 01111이 된다.
• empty : empty는 모든 비트가 0이 되어야하니, 그냥 0으로 만들어 주면 된다.

위처럼 비트연산을 사용해 비트마스크를 만들어 각 원소들을 확인하면 된다. 주의할 점은 백준에서 Pypy3를 사용하면 메모리초과가 발생하여 해결할 수 없다. 질문 결과 PyPy3로 문제를 맞힌사람은 하나도 없다고 한다. 그래서 Python3를 사용해서 제출을 한다면 문제를 맞힐 수 있다는 것을 참고해야한다.

코드

# 11723번 집합
import sys

# main
m = int(sys.stdin.readline())

bit = 0
for _ in range(m):
    command = sys.stdin.readline().split()

    if command[0] == "all":
        bit = (1 << 20) - 1
    elif command[0] == "empty":
        bit = 0
    else:
        op = command[0]
        num = int(command[1]) - 1

        # add
        if op == 'add':
            bit |= (1 << num)
        # remove
        elif op == 'remove':
            bit &= ~(1 << num)
        # check
        elif op == 'check':
            if bit & (1 << num) == 0:
                print(0)
            else:
                print(1)
        # toggle
        elif op == 'toggle':
            bit = bit ^ (1 << num)