백준 11723번 바로가기

첫 번째 풀이

s = set()

for _ in range(int(input())):
  cmd = input().split()
  if len(cmd) == 1:
    if cmd == ['all']:
      s = set([i+1 for i in range(20)])
    elif cmd == ['empty']:
      s = set()
  else:
    do=cmd[0]
    num=cmd[1]
    if do == 'add':
      s.add(num)
    elif do == 'remove':
      if num in s:
        s.discard(num)
    elif do == 'check':
      if num in s:
        print(1)
      else:
        print(0)
    elif do == 'toggle':
      if num in s:
        s.discard(num)
      else:
        s.add(num)

두 번째 풀이

import sys
s = 0

for _ in range(int(sys.stdin.readline())):
  cmd = sys.stdin.readline().split()
  if cmd == ['all']:
    s = (1 << 20) - 1
  elif cmd == ['empty']:
    s = 0
  else:
    do=str(cmd[0])
    num=int(cmd[1]) - 1
    if do == 'add':
      s |= (1 << num)
    elif do == 'remove':
      s &= ~(1 << num)
    elif do == 'check':
      print(0 if s & (1 << num) == 0 else 1)
    elif do == 'toggle':
      s ^= (1 << num)

CODE REVIEW

  1. 첫 번째 풀이에서는 set()을 이용하여 문제를 풀었는데, 시간초과 에러가 발생했다… 시간복잡도가 O(1)인 set도 이렇다니… 문제의 제목인 ‘집합’과 다르게 집합과 다른 걸 사용해야하나?? -> pypy3으로 제출해도 여전히 시간 초과… 에휴!
  2. 도저히 답을 못찾겠어서 구글링을 하다가 비트마스킹(bitmasking)기법에 대해 알게 되었다. 0과 1로 이루어진 이진법 숫자를 이용하여 위치와 숫자를 1:1대응해서 풀어내는 방식이었다.
  3. 두 번째 풀이에서는 시간을 줄이기 위해 input()대신 sys.stdin.readline()을 사용했고, bitmasking 이용해서 문제를 풀어내었다.
    • bitmasking에 대한 자료는 아래 REFERENCE를 참조!
    • 전에 HEAD FIRST JAVA 책을 읽다가 부록에서 OR XOR AND 비트 밀어내기에서 봤던 내용들인데 간만에 보니까 반가웠다.
  4. 다시 풀어보니 set()을 이용하는 경우에도 sys.stdin.readline()을 이용하면 시간 초과 없이 풀리긴 하더라…ㅂㅇㅂ

REFERENCE