[파이썬(Python)] 백준 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 연산이 주어질때마다, 결과를 출력한다.

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

이 문제는 공집합 S에서 특정 연산을 수행하는 프로그램을 작성하는 문제입니다. 주어진 연산의 종류는 다음과 같습니다. 

• add x: x를 집합 S에 추가 (1 ≤ x ≤ 20)
• remove x: x를 집합 S에서 제거 (1 ≤ x ≤ 20)
• check x: x가 집합 S에 있으면 1, 없으면 0 출력
• toggle x: x가 집합 S에 있으면 제거, 없으면 추가
• all: {1, 2, ..., 20}으로 설정
• empty: S를 공집합으로 설정

 

연산의 개수 M이 최대 3,000,000이므로 빠른 연산 및 입출력 최적화가 필요합니다. 

 

 

 

 

 

 

 

 

 

💡 해결 방법

 

 

 

1️⃣ 비트 마스킹(Bit Masking)이란?

 

비트 마스킹(Bit Masking)은 정수를 이진수로 표현하여 특정 상태를 저장하고 조작하는 기법입니다. 이 문제에서처럼 고정된 크기의 집합을 다룰 때 효율적입니다.

• 하나의 정수를 이진수로 변환하여 1 ~ 20까지의 숫자 포함 여부를 저장합니다.
• 숫자 x가 집합에 포함되었는지를 x번째 비트(0 또는 1)로 표현 가능

 

 

📌 예시: 집합 S = {1, 3, 4, 8}

00000000 00001001 0001 (3, 4, 8번 비트가 1)

 

 

 

 

 

 

3️⃣ 비트 마스킹을 통한 연산 구현 

 

✅ add x (집합에 추가) → S |= (1 << (x-1))

• (1 << (x-1)): x번째 비트를 1로 만든 값
• S |= 연산 → 기존 S에서 해당 위치의 비트가 1로 설정

 

📌 예시: S = 00000000 00000001 

S = 00000000 00000001  (1 포함)
add 3 실행
1 << (3-1) → 00000000 00000100  (3번째 비트만 1)
S |= 00000000 00000100 → 00000000 00000101  (1과 3 포함)

 

 

 

 

 

✅ remove x (집합에서 제거) →  S &= ~(1 << (x-1))

• (1 << (x-1)): x번째 비트만 1인 값
• ~(1 << (x-1)): x번째 비트만 0, 나머지는 1
• S &= 연산 → 기존 S에서 해당 위치의 비트가 0으로 설정

 

📌 예시: S = 00000000 00000101

S = 00000000 00000101  (1과 3 포함)
remove 3 실행
1 << (3-1) → 00000000 00000100
~(1 << (3-1)) → 11111111 11111011 (3번째 비트만 0)
S &= 11111111 11111011 → 00000000 00000001  (1만 포함)

 

 

 

 

 

✅ check x (숫자 존재 여부 확인) → (S & (1 << (x-1))) != 0

• (1 << (x-1)): x번째 비트가 1인 값입니다.
• S & 연산 → 해당 비트가 1이면 결과가 0이 아님
  • 존재하면 1 출력, 없으면 0 출력

 

📌 예시:  S = 00000000 00000101

S = 00000000 00000101 (1과 3 포함)
check 1 → (S & 00000000 00000001) != 0 → 1
check 2 → (S & 00000000 00000010) == 0 → 0

 

 

 

 

 

✅ toggle x (토글) → S ^= (1 << (x-1))

• S ^= (1 << (x-1)) →  비트가 반전됨
  • 1이면 0으로, 0이면 1로 변환

 

📌 예시:  S = 00000000 00000101 (1과 3 포함)

S = 00000000 00000101 (1과 3 포함)
toggle 3 실행 → 00000000 00000101 ^ 00000000 00000100 → 00000000 00000001 (3 제거)
toggle 2 실행 → 00000000 00000001 ^ 00000000 00000010 → 00000000 00000011 (2 추가)

 

 

 

 

 

✅ all (전체 집합) → S = (1 << 20) - 1

• (1 << 20): 20번째 비트만 1인 값 (100000...000)
• -1을 하면 모든 비트가 1이 됨 → {1, 2, ..., 20} 설정

 

📌 예시

S = 11111111 11111111 111111 (모든 비트 1)

 

 

 

 

 

✅ empty (공집합) → S = 0

• S를 0으로 설정하면 모든 비트가 0이므로 공집합

 

📌 예시

S = 00000000 00000000 (모든 원소 제거)

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

import sys

input = sys.stdin.readline
S = 0  

output = []

for _ in range(int(input().strip())):
    command = input().strip().split()
    if command[0] == "add":
        S |= (1 << (int(command[1]) - 1))
    
    elif command[0] == "remove":
        S &= ~(1 << (int(command[1]) - 1))
    
    elif command[0] == "check":
        sys.stdout.write("1\n" if (S & (1 << (int(command[1]) - 1))) else "0\n")
    
    elif command[0] == "toggle":
        S ^= (1 << (int(command[1]) - 1))
    
    elif command[0] == "all":
        S = (1 << 20) - 1
    
    elif command[0] == "empty":
        S = 0

 

Algorithm/백준/Silver/11723. 집합 at main · kuun1000/Algorithm