Bitmask

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