[백준] 11723번 집합 해설 및 설명 (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. 파이썬에서는 집합(set) 연산을 사용하여 이 문제를 해결할 수 있습니다.
2. 우선 빠른 입력을 통하여 입력을 받습니다.
3. 그 다음 set을 통한 연산 처리를 진행합니다.

• add x: 집합에 x를 추가합니다.
• remove x: x가 존재하면 삭제합니다.
• check x: x가 존재하는지 확인하고 1 또는 0을 출력합니다.
• toggle x: x가 존재하면 삭제, 없으면 추가합니다.
• all: {1, 2, ..., 20} 집합으로 변경합니다.
• empty: 공집합으로 변경합니다.

 

4. 그 이후의 연산은 remove() 대신 discard() 사용했습니다.

remove()는 존재하지 않는 원소를 삭제하려 하면 에러 발생하지만 discard()는 에러 없이 무시할 수 있습니다.

 

all 연산을 set(range(1, 21)) 로 설정하여 빠르게 처리합니다.

empty 연산을 S.clear() 로 처리합니다.

 

시간 복잡도

• O(1)

 

---

 

문제 코드

 

import sys

input = sys.stdin.readline  # 빠른 입력

M = int(input())  # 연산 개수 입력
S = set()  # 집합 S 초기화

for _ in range(M):
    op = input().split()  # 명령어 입력 받기
    if op[0] == 'add':  
        # x를 S에 추가 
        S.add(int(op[1]))
    elif op[0] == 'remove':  
        # x가 S에 존재하면 제거
        S.discard(int(op[1]))  # discard 사용
    elif op[0] == 'check':  
        # x가 S에 존재하면 1, 없으면 0 출력
        print(1 if int(op[1]) in S else 0)
    elif op[0] == 'toggle':  
        # x가 S에 있으면 제거, 없으면 추가
        x = int(op[1])
        if x in S:
            S.remove(x)
        else:
            S.add(x)
    elif op[0] == 'all':  
        # S를 {1, 2, ..., 20} 으로 변경
        S = set(range(1, 21))
    elif op[0] == 'empty':  
        # S를 공집합으로 변경
        S.clear()