[Python 파이썬] 백준 11723번 - 집합

 

2024년 6월 11일

문제 링크 : 백준 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 연산이 주어질때마다, 결과를 출력한다.

 

알고리즘 분류

• 구현
• 비트마스킹

---

 

 

문제 접근

 

문제를 풀고 보니 비트마스킹 개념을 그대로 묻는 문제였음을 깨달았다.

그냥 간단한 구현 문제인 줄 알아서 각 로직을 모듈화하여 단순 구현으로 문제를 풀었다..

 

딕셔너리 자료구조를 선언해, key : value의 key를 1~20으로 세팅, value는 0으로 초기화하여 문제를 풀었다.

문제에서 필요로 하는 연산들이 들어올 때마다 적절하게 딕셔너리를 조작해, 중간중간 check 명령어가 들어올 때마다 출력하는 로직으로 간단히 구성했다.

 

---

입력 예제

 

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
0
1
0
1
0
1
0
1
1
0
0
0
1
0

 

---

전체 코드

 

# 11723
import sys
input = sys.stdin.readline

def add(dict, x):
    dict[x] = 1
    return dict

def check(dict, x):
    return dict[x]

def remove(dict, x):
    dict[x] = 0
    return dict

def toggle(dict, x):
    if dict[x] == 1:
        dict[x] = 0
    else:
        dict[x] = 1
    return dict

def all():
    return {
        "1" : 1, "2" : 1, "3" : 1, "4" : 1, "5" : 1,
        "6" : 1, "7" : 1, "8" : 1, "9" : 1, "10" : 1,
        "11" : 1, "12" : 1, "13" : 1, "14" : 1, "15" : 1,
        "16" : 1, "17" : 1, "18" : 1, "19" : 1, "20" : 1
    }

def empty():
    return {
        "1": 0, "2": 0, "3": 0, "4": 0, "5": 0,
        "6": 0, "7": 0, "8": 0, "9": 0, "10": 0,
        "11": 0, "12": 0, "13": 0, "14": 0, "15": 0,
        "16": 0, "17": 0, "18": 0, "19": 0, "20": 0
    }

def main():
    M = int(input())

    dict = {
        "1": 0, "2": 0, "3": 0, "4": 0, "5": 0,
        "6": 0, "7": 0, "8": 0, "9": 0, "10": 0,
        "11": 0, "12": 0, "13": 0, "14": 0, "15": 0,
        "16": 0, "17": 0, "18": 0, "19": 0, "20": 0
    }

    for _ in range(M):
        op = list(map(str, input().split()))
        if op[0] == "add":
            dict = add(dict, op[1])
        elif op[0] == "check":
            print(check(dict, op[1]))
        elif op[0] == "remove":
            dict = remove(dict, op[1])
        elif op[0] == "toggle":
            dict = toggle(dict, op[1])
        elif op[0] == "all":
            dict = all()
        else:
            dict = empty()

if __name__ == "__main__":
    main()

 

 

---

풀이 후기

 

비트마스킹 개념을 그대로 문제에 녹인걸 뒤늦게 알아버렸으니, 비트마스킹 개념을 숙지한 후 나중에 다시 풀어봐야겠다고 생각했다.