파이썬 비트마스크

백준 11723 집합 문제를 풀던 중...

예제는 맞게 구현했는데

제출해보니 오잉 메모리초과?!

import sys

m = int(sys.stdin.readline())
s = []

for _ in range(m):
    arr = list(sys.stdin.readline().split())

    if arr[0] == 'add':
        if arr[1] not in s:
            s.append(arr[1])

    elif arr[0] =='remove':
        if arr[1] in s:
            s.remove(arr[1])

    elif arr[0] =='check':
        if arr[1] in s:
            print(1)
        if arr[1] not in s:
            print(0)

    elif arr[0]=='toggle':
        if arr[1] in s:
            s.remove(arr[1])
        elif arr[1] not in s:
            s.append(arr[1])

    elif arr[0]=='all':
        s = ['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','16','17','18','19','20']

    elif arr[0] =='empty':
        s = []

오잉 메모리 초과?!

 

 

알고보니 푸는 방법이 틀렸다

비트마스크를 활용해야 하는 문제였던것

 

비트마스크는 시간복잡도가 o(1)이다

메모리도 더 적게 사용함

 

기본적인

& | ^ ~ >> <<는 알지만 실제 코드 쓸 때 적용해본적은 없다

이번 기회에 배우는걸로~~

 

 

 

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

s |= (1<<x)

 

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

s &= ~(1<<x)

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

if s & (1<<x) ==0 : print(1)

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

s ^= (1<<k)

• all: S를 {1, 2, ..., 20} 으로 바꾼다.

s = (1 << 20) - 1-> 1부터 20까지 모든비트 1로 설정

• empty: S를 공집합으로 바꾼다.

s = 0

 

 

 

완성코드

주의!!!!!!!!!!!!!! pypy로 제출하면 계속 메모리 초과가 뜬다

python3으로 제출해야함

import sys

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

for _ in range(m):
    arr = sys.stdin.readline().split()
    if arr[0] == "all":
        s = (1 << 20) -1

    elif arr[0] == "empty":
        s = 0

    else:
        x = int(arr[1]) - 1

        if arr[0] == 'add':
            s |= (1 << x)

        elif arr[0] =='remove':
            s &= ~(1 << x)

        elif arr[0] =='check':
            if s & (1 << x) == 0:
                print(0)
            else:
                print(1)

        elif arr[0]=='toggle':
            s = s ^ (1<<x)