[BOJ/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 연산이 주어질때마다, 결과를 출력한다.

 

예제 입력 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

---

풀이

 

우선 집합 연산을 수행하는 문제이기 때문에, set 자료형을 이용하여 문제를 해결했다.

import sys
 
m = int(sys.stdin.readline())
s = set()
 
for _ in range(m):
    req = sys.stdin.readline().split()
    if req[0]=='add':
        s.add(int(req[1]))
    elif req[0]=='remove':
        if int(req[1]) in s:
            s.remove(int(req[1]))
    elif req[0]=='check':
        if int(req[1]) in s:
            print(1)
        else:
            print(0)
    elif req[0]=='toggle':
        if int(req[1]) in s:
            s.remove(int(req[1]))
        else:
            s.add(int(req[1]))
    elif req[0]=='all':
        s = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
    else:
        s = set()

 

1. 공집합 s를 만든다.
2. m번만큼 반복하여 입력을 받는다.
3. 입력 받은 값이 'add 5'일 경우, split으로 쪼개어 'add'임을 확인하고, '5'를 정수형인 5로 바꾼 뒤, 집합에 추가한다.
4. 마찬가지 방식으로 입력 받은 값이 'remove 5'일 경우, 'remove'임을 확인하고, 집합에 5가 있을 경우 제거한다.
5. 입력받은 값이 'check 5'일 경우, 집합에 5가 있을 경우 1을 출력, 아닐 경우 0을 출력한다.
6. 입력받은 값이'toggle 5'일 경우, 집합에 5가 있을 경우 제거하고, 없을 경우 추가해준다.
7. 입력받은 값이 'all'일 경우, 집합을 {1,2,...,20}으로 바꾼다.
8. 그것도 아니라면(입력 값이 empty라면), 집합을 공집합으로 바꾼다.

이런 방식으로 문제를 해결할 수 있지만, 비트마스킹을 통한 문제풀이 또한 가능하다.

import sys
 
m = int(sys.stdin.readline())
s = 0
 
for _ in range(m):
    req = sys.stdin.readline().split()
    if req[0]=='add':
        s = s|(1<<int(req[1]))
    elif req[0]=='remove':
        s = s & ~(1<<int(req[1]))
    elif req[0]=='check':
        if (s & (1<<int(req[1])))==0:
            print(0)
        else:
            print(1)
    elif req[0]=='toggle':
        s = s ^ (1<<int(req[1]))
    elif req[0]=='all':
        s = (1<<21) - 1
    else:
        s = 0

• 이 코드에 사용된 비트 연산에 대한 설명은 아래 게시물에서 확인할 수 있다.

비트마스크, 비트마스킹(BitMasking)이란