[백준 16903번] 수열과 쿼리 - 20 (Python3)

import sys
input = sys.stdin.readline

def update(x,v):
  now = trie
  for i in reversed(range(30)):
    b = (x>>i)&1
    if not now.get(b):
      now[b] = {}
    now = now[b]
    if not now.get(-1):
      now[-1] = 0
    now[-1] += v

def find(x):
  r = ""
  now = trie
  for i in reversed(range(30)):
    b = ((x>>i)&1)^1
    if now.get(b) and now[b][-1]:
      r += "1"
      now = now[b]
    else:
      r += "0"
      now = now[b^1]
  return int(r,2)

N = int(input())
trie = {}
update(0,1)
for _ in range(N):
  q,x = map(int,input().split())
  if q==3:
    print(find(x))
  else:
    update(x,3-q*2)

트라이로 해결하였다.

입력 숫자의 범위가 10^9로 매우 크기 때문에 그냥 배열을 생성하면 메모리 초과가 발생하게 된다.

 

풀이를 설명하면,

1. 입력받은 숫자를 2진법 문자열로 취급하여 트라이로 저장한다. 이때 각 값에서 -1 인덱스는 해당 비트의 개수를 의미한다.

2. 숫자를 제거하는 경우에는 트라이에서 각 자리수의 -1 인덱스를 -1해준다.

3. find 함수로 XOR 최댓값을 찾고 출력한다. 트라이를 이용하여, 가장 큰 자릿수부터 XOR 1이 가능하면 XOR 1을 탐색, 아니면 XOR 0을 탐색하여 가장 큰 값을 찾는다. 만약 -1 인덱스값이 0인 경우에는 제거된 숫자이므로 탐색하지 않아야한다.

 

트라이를 이용해야한다는 것을 알면 쉽게 해결할 수 있는 문제이지만 트라이를 이용해야한다는 것을 알아내기 쉽지 않은 문제이다.

 

 

오늘의 교훈) 트라이는 다양하게 활용할 수 있다.