11723_집합

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

11723번: 집합

 

 

 

비트마스크를 공부해볼 수 있는 문제였다.

 

비트마스크란 쉽게 생각해서 배열들을 하나의 수로 나타낼 수 있는 기법이다.

 

예를들어서

 

{1 , 3 , 4 } 라는 배열이 있다고 생각해보자. 이를 2진수로 나타내면

 

1101 이런식으로 나타낼 수 있을 것이다. 1,3,4가 들어있기에 1,3,4번째 2진수가 1로 변환

이진수는 결국 십진수로 나타낼 수 있으므로 1,3,4 가들어있는 배열을 2진수로 나타낼 수 있는 것이다.

 

그렇다면 문제에서 원하는 연산들은 다 비트연산처리를 해서 표현할 수 있다.

 

import sys
input = sys.stdin.readline
m = int(input())
S=0
for _ in range(m):
    order = input().rstrip()

    if order =="all":
        S = (1<<20)-1;
    elif order =="empty":
        S = 0;
    else:
        order,num = order.split()
        num = int(num)-1

        if order=="add":
            S |= (1<<num)
        elif order=="check":
                print(1 if S & (1<<num) else 0)
        elif order=="toggle":
            S ^= (1<<num)
        elif order=="remove":
            S &= ~(1<<num)

 

 

해당문제는 pyp3로 풀면 풀리지 않는다... 그리고 이러한 방식보다 그냥 리스트를 만들어서 해결해도 메모리 제한이 걸리지 않아 풀리긴 하나, 그래도 비트마스크가 무엇인지 이해하고 풀어보는거에 의미를 두었다.