[python] 백준 11723번 집합

https://www.acmicpc.net/problem/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 연산이 주어질때마다, 결과를 출력한다.

예제 입력 1 복사

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1 복사

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0

 

 

이 문제에 처음 접근했을 때에는 단순히 리스트에 명령어에 따라 값을 추가, 제거 등 실행시켜야겠다고 생각을 했다가, 

아래에 알고리즘 분류 중 "비트마스킹" 이 있어 해당 알고리즘으로 풀어보았다.

 

 

우선 비트 마스킹이란 컴퓨터 내에서는 모두 이진수로 표현하는 특성을 이용하여,

정수의 이진수 표현을 자료구조로 쓰는 기법을 의미한다.

 

해당 알고리즘을 사용하기 위해서 비트 연산자를 알아야하는데 , and(&), or(|), xor(^), shift(<<,>>), not(~)이 있다.

 

이 문제는 1~20 까지의 숫자만 사용한다.

아주 적은 범위의 수만 사용하므로, 배열을 이용하는 것보다, 비트 메모리를 이용하는 것이 훨씬 빠르다

 

00000000.. 이렇게 20칸이있다고 가정하고,

add의 경우

1이 들어오면 00000.. 0001,

2가 들어오면 00000.. 0011,

이런식으로 1을 넣어주면 된다.

S = 0
S |= 1<<(x-1)

이렇게 하면 2의 경우 1칸 1을 왼쪽으로 이동시키는 것이므로 두번째 칸에 1을 채울 수 있다

 

remove의 경우 입력받은 수의 칸을 0으로 삭제 시켜야 하므로

S가 000..0111 일때 (1,2,3이 입력된 상황) 3을 삭제 해야한다면,

0111 과 0100을 연산해서 0011을 만들어야한다.

따라서 ~0100 = 1011과 0111을 and 처리하면 같은 부분만 1로 바뀌므로, 아래와 같이 작성하면 된다.

S &= ~(1<<x)

 

 

다음 check의 경우 해당 칸이 1인지를 확인하는 것이므로 

0111과 0100을 and 했을때, 0이라면 없는것, 그게 아니면 있는것이므로 아래와 같이 작성이 가능하다

if S&(1<<x):
            print(1)
        else:
            print(0)

 

toggle의 경우 check와 마찬가지로 검사를 한 후, 존재하면 0100 과 0111 -> 0011 이런식으로 없애면 됨

remove에서 사용한걸 그대로 써도 되지만, 이미 조건 검사를 하기 때문에  xor을 이용하여 구현해보았다.

if S&(1<<x):
            S ^= 1<<x
        else:
            S |= 1<<x

 

마지막 all과 empty는 모두 1로 채우거나 0으로 만드는 것이므로 아래와 같이 작성하면 된다.

S = (1<<20)-1 	#all
S = 0	#empty

 

 

---

 

 

정답 코드

import sys
input = sys.stdin.readline
S = 0
M = int(input())
for _ in range(M):
    rule = input()
    if 'add' in rule:
        x = int(rule[4:])-1
        S |= 1<<x
    elif 'remove' in rule:
        x = int(rule[7:])-1
        S &= ~(1<<x)
    elif 'check' in rule:
        x = int(rule[6:])-1
        if S&(1<<x):
            print(1)
        else:
            print(0)
    elif 'toggle' in rule:
        x = int(rule[7:])-1
        if S&(1<<x):
            S ^= 1<<x
        else:
            S |= 1<<x
    elif 'all' in rule:
        S = (1<<20)-1
    elif 'empty' in rule:
        S = 0