[Python] 백준 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를 공집합으로 바꾼다. 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

 

메모리 제한

• Java 8: 448 MB
• Java 8 (OpenJDK): 448 MB
• Java 11: 448 MB
• Kotlin (JVM): 448 MB
• C#: 64 MB
• Java 15: 448 MB
• F#: 64 MB
• Visual Basic: 64 MB

---

문제만 보면 간단해보인다. 

스택이나 큐를 쓰는것도 아니고 그냥 리스트에 저장했다 뺏다 단순해 보이지만

 

단순하게 풀면... 시간초과가 반드시 뜨는 문제이다.

 

import sys
m = int(sys.stdin.readline())
s = []
for _ in range(m):
    o = sys.stdin.readline().rstrip().split()
    if o[0] == "all":
        s.clear()
        for i in range(20):
            s.append(int(i+1))
    elif o[0] == "empty":
        s.clear()
    else:
        order = o[0]
        x = int(o[1])
        if order == "add":
            if x in s:
                continue
            s.append(x)
        elif order == "remove":
            if x in s:
                s.remove(x)
        elif order == "check":
            if x in s:
                print(1)
            else:
                print(0)
        #elif order == "toggle":
        else:
            if x in s:
                s.remove(x)
            else:
                s.append(x)

위와 같이 풀면

 

위의 장면을 볼 수 있게 된다.

 

---

방법을 도저히 못찾겠어서 결국 구글에 검색해봤다.

 

이 문제는 비트마스킹을 이용해서 푸는 문제라고 한다.

 

비트마스킹

비트 (0 과 1의 이진법) 을 이용하며 연산자를 이용하여 계산하는 방식이다.

 

우선 비트마스킹을 이용하기에 앞서 비트 연산자에 대해서 알아야 한다.

 

 

비트 연산자

AND OR NOT XOR 과 같은 연산자가 있다.

 

AND 연산 (&)

대응하는 두 비트가 모두 1일때 1 반환

 

1010 & 1111 = 1010

 

OR 연산 (|)

대응 하는 두 비트 중 하나라도 1일 때 1 반환

 

1010 | 1111 = 1111

 

XOR 연산 (^)

대응하는 두 비트가 서로 다르면 1 반환

 

1010 ^ 1111 = 0101

 

NOT 연산 (~)

비트의 값을 반전시켜 반환

 

~1010 = 0101

 

왼쪽/오른쪽 Shift

왼쪽 쉬프트 : 비트를 왼쪽으로 옮김 (<<) 

오른쪽 쉬프트 : 비트를 오른쪽으로 옮김(>>)

 

00001010 << 2 = 00101000

00001010 >> 2 = 00000010

 

이제 비트마스킹의 연산법은 알았다.

 

문제를 풀어보자

 

원소 추가 (add)

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.

위의 연산을 하기 위해서는

 

S = S | (x << num)

 

x 를 num 만큼 왼쪽 쉬프트 해준 값이 x가 된다.

 

예를 들어

 

S = 10000000000000000000 인데

x = 19이면 x = 01000000000000000000 이며

 

S = S | x를 하면 11000000000000000000 이기 때문에 19와 20 이 추가된 걸로 확인 가능하다.

 

이러한 방식으로

 

원소 제거 (remove)

• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.

S를 뒤집으면 없는 숫자 = 1, 있는 숫자 0이 될 것이며 x << num 을 해준 위치와 S = S | x를 해주면 제거가 가능하다.

 

s = s & ~(x << num)

 

원소 확인 (check)

• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)

s & (x << num)

 

num만큼 쉬프트 시킨 연산자가 S와 동일한 위치에 1이 위치하면 값이 존재

 

없다면 값이 없는 것으로 확인 가능하다.

 

토글 (toggle)

• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)

위의 연산들 중 XOR을 사용하면 된다.

 

XOR은 둘 중 하나가 1이어야 하며 둘 다 0 혹은 1이면 0을 반환하는 성질을 이용하여 준다.

 

s ^ (x << num)

 

import sys
m = int(sys.stdin.readline())
s = 0b0
for _ in range(m):
    o = sys.stdin.readline().rstrip().split()
    if o[0] == "all":
        s = 0b111111111111111111111
    elif o[0] == "empty":
        s = 0b0
    else:
        order = o[0]
        x = int(o[1])
        if order == "add":
            s = s | (0b1 << x)
        elif order == "remove":
            s = s & ~(0b1 << x)
        elif order == "check":
            if s & (0b1 << x):
                print(1)
            else:
                print(0)
        #elif order == "toggle":
        else:
            s = s ^ (0b1 << x)

 

 

 

참고

https://coarmok.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACpython-%EB%B0%B1%EC%A4%80-11723%EB%B2%88-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%82%B9

[파이썬python] 백준 11723번 - 비트마스킹

https://velog.io/@1998yuki0331/Python-%EB%B9%84%ED%8A%B8-%EB%A7%88%EC%8A%A4%ED%82%B9-%EC%A0%95%EB%A6%AC

[Python] 비트 마스킹 정리