[백준/16930] 수열과 쿼리 20

Problem : https://www.acmicpc.net/problem/16903

16903번: 수열과 쿼리 20

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

0이 하나 포함되어 있는 배열 A가 있다. 이때, 다음 쿼리를 수행해야 한다.

1 x: A에 x를 추가한다.
2 x: A에서 x를 제거한다. A에 x가 두 개 이상 있는 경우에는 하나만 삭제한다. 항상 A에 x가 있는 쿼리만 주어진다.
3 x: A에 포함된 각각의 원소와 x를 XOR 연산을 한 다음, 가장 큰 값을 출력한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 쿼리의 개수 M(1 ≤ M ≤ 200,000)이 주어진다. 둘째 줄부터 M개의 줄에 쿼리가 주어진다. 입력으로 주어지는 x의 범위는 109보다 작거나 같은 자연수이다.

3번 쿼리는 하나 이상 주어진다.

 

출력

 

쿼리를 수행한 결과를 출력한다.

 

입력 예시

 

10
1 8
1 9
1 11
1 6
1 1
3 3
2 8
3 3
3 8
3 11

 

출력 예시

 

11
10
14
13

 

 

---

 

풀이

 

트라이 자료구조를 사용해보자. 우리가 저장 및 삭제하는 수는 2진법의 형태로 나타낼 수 있고, 최대 x의 범위는 10^9 <= 2^30이므로 총 depth 30의 바이너리 트라이 구조로 모든 수를 저장할 수 있다.

 

• 삽입 연산은 해당하는 수의 이진법 배열에 맞게 저장하면 된다.
• 삭제 연산 역시 삽입 연산과 동일하다. 이 때, 탐색 도중 리프 노드가 1임을 확인하는 순간에 그 노드와 그 하위 노드 전체를 삭제함으로써 시간을 더 줄일 수 있다.
• 검색 연산은 x값을 기준으로 검색한다. x값의 현재 이진법상 자릿수가 1이라면, 그 자릿수가 0인 숫자들이 xor 결과가 더 크다. 반대로 자릿수가 0이라면, 그 자릿수가 1인 숫자들이 xor 결과가 클 것이다. 이를 염두해 두고 우선순위대로 탐색을 실행하면 된다.
• 삽입, 삭제, 검색 연산 모두 최대 O(1)의 시간복잡도가 소요된다. 즉 총 시간복잡도는 O(M)이다.

 

풀이 코드

import sys
input = sys.stdin.readline

MAX = 29
trie = {}

def add(num) :
  cur = trie
  for i in range(MAX, -1, -1) :
    tar = 1 if num & (1 << i) else 0
    if tar not in cur :
      cur[tar] = { 2 : 1 }
    else :
      cur[tar][2] += 1
    cur = cur[tar]

def delete(num) :
  cur = trie
  for i in range(MAX, -1, -1) :
    tar = 1 if num & (1 << i) else 0
    cur[tar][2] -= 1
    if not cur[tar][2] :
      del cur[tar]
      return
    cur = cur[tar]

def search(num) :
  cur = trie
  res = 0
  for i in range(MAX, -1, -1) :
    flg = num & (1 << i)
    _range = [0, 1] if num & (1 << i) else [1, 0]
    for j in _range :
      if j in cur :    
        break
    if j and not flg or not j and flg :
      res += 1 << i
    cur = cur[j]
  print(res)

M = int(input())
add(0)
for _ in range(M) :
  q, x = map(int, input().split())
  if q == 1 :
    add(x)
  elif q == 2 :
    delete(x)
  else :
    search(x)

풀이 완료!