[백준 11723번] 집합 - python

문제 링크

https://www.acmicpc.net/problem/11723

11723번: 집합

풀이 

- set을 사용하여 명령어에 해당하는 작업을 처리해주니 시간초과 발생 

- pypy3으로 실행할 때는 메모리 초과가 발생  

# 시간 초과 
import sys
input = sys.stdin.readline

n = int(input())

data = set()
for _ in range(n):
  s = input().split()

  if s[0] == 'add':
    data.add(int(s[1]))
  elif s[0] == 'remove':
    data.discard(int(s[1]))
  elif s[0] == 'check':
    if int(s[1]) in data:
      print(1)
    else:
      print(0)
  elif s[0] == 'toggle':
    if int(s[1]) in data:
      data.dicard(int(s[1]))
    else:
      data.add(int(s[1]))
  elif s[0] == 'all':
    data = set(i+1 for i in range(20))
  else:
    data = set()

- 질문을 찾아보니 비트 마스킹을 사용해야 한다고 한다. 

- 본 문제에서는 1부터 20까지의 숫자만 다룬다.

따라서 s = [0] * 21 를 만들어준다.

s[i] 가 1일 경우 i라는 숫자가 존재한다는 것이고

s[i]가 0일 경우 i라는 숫자가 없다는 것을 의미한다. 

import sys
input = sys.stdin.readline

n = int(input())

s = [0] * 21 
for _ in range(n):
  c = input().split()
  
  # 명령어의 길이에 따라 
  if len(c) == 1 :
    command = c[0]
  else:
    command = c[0]
    num = int(c[1])
 
  # 존재함을 표시하는 1
  if command == 'add':
    s[num] = 1 
  # 없음을 표시하는 0 
  elif command == 'remove':
    s[num] = 0
  elif command == 'check':
    if s[num] == 1 :
      print(1)
    else:
      print(0)
  elif command == 'toggle':
    if s[num] == 1 :
      s[num] = 0 
    else:
      s[num] = 1
  # 모두 존재 
  elif command == 'all':
    s = [1] * 21 
  # 공집합 
  else:
    s = [0] * 21