[백준] 11723 집합 (파이썬 비트마스크)

https://www.acmicpc.net/problem/11723

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를 공집합으로 바꾼다. 

---

풀이 과정

이 문제는 파이썬의 집합 set을 이용해 단순 구현으로 풀 수도 있고

비트마스크를 이용해 풀 수도 있다.

 

단순 구현방식은 단순히 구현만 하면 되므로, 비트마스크를 이용한 풀이를 소개하려고 한다.

 

집합 내에 속한 1부터 20까지의 숫자를

비트의 각 자리로 매칭시키자.

 

예를 들어, {1, 2, 5, 6} 이라면

110011 로 표기함으로써 1, 2, 5, 6번째에만 1을 넣어주어 집합에 포함되어 있는 수를 표현할 수 있다.

 

그래서 문제에서 주어진 연산은 다음과 같이 구현할 수 있다.

• all : 1부터 20까지의 자리에 1을 넣어준다.
• empty : 비트의 모든 자리를 0으로 만든다.
• add : 비트의 해당 자리를 1로 만든다.
• remove : 비트의 해당 자리를 0으로 만든다.
• check : 비트의 해당자리가 1인지 0인지 확인한다.
• toggle : 비트의 해당 자리 수를 바꾼다 ( 1 ->0 / 0 -> 1 )

import sys

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

bit = 0
for i in range(m):
    comm = sys.stdin.readline().rstrip().split()

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

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

        elif op == "toggle":
            bit = bit ^ (1 << num)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !