백준 11723번 : 집합 in Python

11723번: 집합

 

www.acmicpc.net

이 문제는 공집합이 주어졌을 때 여러 연산을 수행하는 프로그램을 만드는 문제이다.

만약 연산의 수가 적은 경우에는 길이가 20인 배열을 만들어서 각 연산을 구현하면 되지만, 연산의 수가 최대 300만 번까지 주어지기 때문에 이를 시간 내에 구현하려면 다른 방식으로 집합을 나타내야 한다.

그래서 여기서는 비트 자료형을 사용해 집합을 나타낸다. 예를 들어 1~20까지 들어갈 수 있는 집합에 3, 5, 7, 9가 들어있으면 이 집합을 비트 표현으로 00000000000101010100로 나타낸다. 즉, 비트 자료형의 각 자리수가 1인 경우 집합 내에 자리수에 해당하는 수가 들어있다는 것을 의미한다.

이렇게 집합을 표현하면 위 문제에서 주어지는 연산을 O(1) 시간 내에 해결할 수 있다. 집합을 표현한 비트 자료형을 S라고 하자. all 연산은 S를 (1<<21)-1로 바꾼다. 1<<21은 1*2=2를 21제곱을 한 결과로, 여기서 1을 빼서 비트 자료형으로 나타내면 1이 20개인 수(11111111111111111111)가 된다. empty 연산은 S를 0으로 바꾼다.

연산에 어떤 수가 동반된 경우 우선 x를 비트 자료형으로 표현한다.  add 연산은 S | x, remove x는 S & ~x, check 연산은 S & x, toggle 연산은 S ^ x를 통해 구현한다. 

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
M = int(input())
S = 0
for _ in range(M):
    command = input().strip().split()
    if command[0] == "all":
        S = (1<<21)-1
    elif command[0] == "empty":
        S = 0
    else:
        num = 1 << (int(command[1])-1)
        if command[0] == "add":
            S = S | num
        elif command[0] == "remove":
            S = S & ~num
        elif command[0] == "check":
            print(1 if S & num > 0 else 0)
        elif command[0] == "toggle":
            S = S ^ num