[백준] 11723 - 집합

문제

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

---

코드

import sys


input = sys.stdin.readline

ALL_SET = int("0b{}".format("1" * 20), 2)
EMPTY_SET = int("0b{}".format("0" * 20), 2)


def solution():
    m = int(input())

    cur_set = EMPTY_SET
    for _ in range(m):
        args = input().split()
        cur_set = task(args, cur_set)


def task(args: list[str], cur_set: int):
    operation = args[0]

    if operation in ("add", "remove", "check", "toggle"):
        x = int(args[1])
        bit = get_bit_from_position(x)
        if operation == "add":
            cur_set = cur_set | bit

        elif operation == "remove":
            cur_set = cur_set & ~bit

        elif operation == "check":
            if cur_set & bit:
                print("1")
            else:
                print("0")

        elif operation == "toggle":
            cur_set = cur_set ^ bit
    else:
        if operation == "all":
            cur_set = ALL_SET

        elif operation == "empty":
            cur_set = EMPTY_SET

    return cur_set


def get_bit_from_position(bit_position: int) -> int:
    bit = 1 << (bit_position - 1)

    return bit


if __name__ == "__main__":
    solution()

해설

• 최대 3,000,000회의 입력이 주어지기 때문에 sys.stdin.readline을 사용하여 입력을 받는다.
• 집합의 상태를 20개의 비트를 사용하여 표현한다. 예를 들어 집합에 1이 들어있는 경우 첫번째 비트는 1이 되고, 들어있지 않는 경우 첫번째 비트는 0이 된다.
• 각 연산 별로 아래와 같은 과정을 수행한다.
  • add : x번째 위치의 비트만 1이고 나머지는 0인 수와 OR 연산을 하면 해당 비트는 0과 1에 상관 없이 1 값을 갖고 나머지는 비트 값을 그대로 유지한다.
  • remove : x번째 위치의 비트만 0이고 나머지는 1인 수와 AND 연산을 하면 해당 비트는 0일 때 1로, 1일 때 0으로 값이 변하고 나머지는 비트 값을 그대로 유지한다. 따라서 x번째 위치의 비트만 1인 수를 먼저 계산하고 NOT 연산을 통해 반전한 뒤 AND 연산을 적용한다.
  • check : x번째 위치의 비트만 1이고 나머지는 0인 수와 AND 연산을 하면 해당 위치의 비트가 0일 때는 0 값, 1일 때는 2 ^ (x - 1) 값을 갖는다. 따라서 해당 연산 값이 0보다 큰 경우 "1"을 출력, 0인 경우 "0"을 출력하도록 한다.
  • toggle : x번째의 위치의 비트만 1이고 나머지는 0인 수와 XOR 연산을 하면 해당 위치의 비트는 0일 때는 1 값, 1일 때는 0 값을 갖고, 나머지 비트는 값을 유지한다.
  • all : 미리 전역 변수로 선언한 ALL_SET을 현재 집합에 할당한다.
  • empty : 미리 전역 변수로 선언한 EMPTY_SET을 현재 집합에 할당한다.