[Python][백준] 11723번 집합 문제 풀이 | 비트마스킹이 뭐여

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

11723번: 집합

이 문제는 정말 어려웠다

무수한 메모리 초과 세례

이 문제는 '비트마스킹'이라는 것을 모르면 메모리 초과의 늪에 빠지는 문제이다.

다른 사람들은 Python의 set 자료구조를 이용하여 풀기도 하던데, 그것은 문제의 출제의도와 다른 것 같으니 배제하고 비트마스킹을 이용한 풀이를 소개하겠다.

 

비트마스킹이란?

비트마스킹(Bitmasking)은 비트, 즉 0과 1, True와 False를 이용하여 문제를 해결하는 것이다.

 

11723번 문제의 조건을 보면 공집합 S에 들어가는 x는 (1 ≤ x ≤ 20)이다.

즉 집합 S는 아래와 같은 그림으로 표현할 수 있다.

 

비트마스킹

 

이것을 이진수로 저장할 수 있지만, 코드의 이해를 위하여, 리스트로 표현하였다.

아래 코드는 실제로 필자가 제출한 코드이다.

import sys


def P11723():
    input = sys.stdin.readline
    s = [False for _ in range(21)]  # 비트마스킹

    lines = int(input())
    for _ in range(lines):
        command = list(input().strip().split())  # strip() 추가(개행문자 제거)
        if len(command) == 2:
            command[1] = int(command[1])

        if command[0] == "add":
            if not s[command[1]]:  # x가 이미 있는 경우에는 연산을 무시. False일 때만 실행
                s[command[1]] = True
        elif command[0] == "remove":
            if s[command[1]]:
                s[command[1]] = False
        elif command[0] == "check":
            print(1 if s[command[1]] else 0)
        elif command[0] == "toggle":
            if s[command[1]]:
                s[command[1]] = False
            else:
                s[command[1]] = True
        elif command[0] == "all":
            s = [True for _ in range(21)]
        elif command[0] == "empty":
            s = [False for _ in range(21)]


if __name__ == '__main__':
    P11723()

import sys


def P11723():
    s = [False]*21  # 비트마스킹
    for _ in range(int(input())):
        command = list(input().strip().split())  # strip() 추가(개행문자 제거)
        if len(command) == 2:
            command[1] = int(command[1])

        if command[0] == "add":
            if not s[command[1]]:  # x가 이미 있는 경우에는 연산을 무시. False일 때만 실행
                s[command[1]] = True
        elif command[0] == "remove":
            if s[command[1]]:
                s[command[1]] = False
        elif command[0] == "check":
            print(1 if s[command[1]] else 0)
        elif command[0] == "toggle":
            if s[command[1]]:
                s[command[1]] = False
            else:
                s[command[1]] = True
        elif command[0] == "all":
            s = [True] * 21
        elif command[0] == "empty":
            s = [False] * 21


if __name__ == '__main__':
    input = sys.stdin.readline
    P11723()