[BOJ] 집합 - 11723 (S5)

시간 제한	메모리 제한
1.5 초	4 MB

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다.
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다.
• all: S를 {1, 2, …, 20}으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

풀이

이 문제는 집합 자료구조의 기본 연산을 구현하는 문제이다. 파이썬의 set을 사용하면 간단하게 해결할 수 있다.

접근 방법

파이썬의 내장 set 자료구조를 사용하면 모든 연산을 효율적으로 처리할 수 있다.

주의사항

M이 최대 3,000,000으로 매우 크기 때문에 빠른 입출력을 사용해야 한다:

• sys.stdin.readline()으로 입력
• sys.stdout.write()로 출력

일반 input()과 print()를 사용하면 시간 초과가 발생할 수 있다.

코드

import sys
input = sys.stdin.readline
print = sys.stdout.write

m = int(input())

s = set()

for _ in range(m):
    command = input().strip().split()

    if len(command) == 2:
        command, x = command
        command = command.strip()
        x = int(x)
    else:
        command = command[0]

    if command == 'add':
        s.add(x)
    elif command == 'remove':
        if x in s:
            s.remove(x)
    elif command == 'check':
        if x in s:
            print('1\n')
        else:
            print('0\n')
    elif command == 'toggle':
        if x in s:
            s.remove(x)
        else:
            s.add(x)
    elif command == 'all':
        s = {i for i in range(1, 21)}
    elif command == 'empty':
        s = set()

코드 설명

빠른 입출력 설정

import sys
input = sys.stdin.readline
print = sys.stdout.write

• sys.stdin.readline()은 input()보다 빠름
• sys.stdout.write()는 print()보다 빠르지만 개행 문자를 자동으로 추가하지 않음

명령어 파싱

command = input().strip().split()

if len(command) == 2:
    command, x = command
    command = command.strip()
    x = int(x)
else:
    command = command[0]

• add, remove, check, toggle은 인자가 있음
• all, empty는 인자가 없음

각 연산 구현

if command == 'add':
    s.add(x)
elif command == 'remove':
    if x in s:
        s.remove(x)
elif command == 'check':
    if x in s:
        print('1\n')
    else:
        print('0\n')
elif command == 'toggle':
    if x in s:
        s.remove(x)
    else:
        s.add(x)
elif command == 'all':
    s = {i for i in range(1, 21)}
elif command == 'empty':
    s = set()

• add: set.add() 사용 (중복 자동 처리)
• remove: 존재 확인 후 제거 (없으면 무시)
• check: in 연산자로 존재 여부 확인
• toggle: 있으면 제거, 없으면 추가
• all: 1부터 20까지의 집합으로 초기화
• empty: 빈 집합으로 초기화

시간 복잡도

• add, remove, check, toggle: O(1) (해시 테이블 기반 set)
• all: O(20) = O(1) (상수)
• empty: O(1)
• 전체: O(M)

M ≤ 3,000,000이지만 각 연산이 O(1)이므로 충분히 빠르다.

비트마스킹을 이용한 풀이

메모리를 더 절약하고 싶다면 비트마스킹을 사용할 수도 있다:

import sys
input = sys.stdin.readline

m = int(input())
s = 0  # 비트마스크

for _ in range(m):
    command = input().strip().split()
    
    if command[0] == 'add':
        x = int(command[1])
        s |= (1 << x)
    elif command[0] == 'remove':
        x = int(command[1])
        s &= ~(1 << x)
    elif command[0] == 'check':
        x = int(command[1])
        print(1 if s & (1 << x) else 0)
    elif command[0] == 'toggle':
        x = int(command[1])
        s ^= (1 << x)
    elif command[0] == 'all':
        s = (1 << 21) - 1
    elif command[0] == 'empty':
        s = 0

비트마스킹 방식:

• add: OR 연산으로 비트 켜기
• remove: AND와 NOT 연산으로 비트 끄기
• check: AND 연산으로 비트 확인
• toggle: XOR 연산으로 비트 반전
• all: 1~20번 비트 모두 켜기
• empty: 0으로 초기화

주의 사항

1. 빠른 입출력: M이 크므로 반드시 sys.stdin.readline() 사용
2. remove 예외 처리: 없는 원소를 제거하려 하면 에러 발생하므로 존재 여부 확인 필요
3. 출력 형식: check 연산만 출력하며, 개행 문자 포함 필요

문제의 의의

이 문제는 집합 자료구조의 기본 연산을 익히고, 대용량 입출력 처리 방법을 배우는 좋은 문제이다. 또한 비트마스킹을 통한 최적화도 경험할 수 있다.