백준 16903번: 수열과 쿼리 20 (Trie)

문제링크:16903번: 수열과 쿼리 20 (acmicpc.net)

16903번: 수열과 쿼리 20

이 문제는 특이하게 배열 A에 원소 x를 추가하거나 원소 x를 제거하거나, 또는 임의의 k가 주여졌을때 A의 임의의 원소 x와 x XOR k 연산을 했을때 얻을 수 있는 최대값을 구해야 하는 문제이다.

 

XOR연산을 하기 위해 원소 x가 주어지면 x를 이진수 배열의 str로 바꾸고, 바꾼 이진수 배열을 시간 복잡도 O(N)으로 처리하기 위해 str를 트라이 형태로 저장하였다. 처음에는 트라이로 최대한 저장공간을 최소화하며 저장하기 위해 바뀐 str를 뒤부터 역순으로 트라이에 저장했는데, 저장공간은 줄어들었지만 역순으로 하면 XOR 연산의 최대값을 구하는 과정이 생각할 수 없을 정도로 매우 매우 복잡해졌다.

 

그래서 여기서 주어지는 x의 최대값은 10^9 로 31개의 이진수 배열 내로 처리 가능한 숫자들이기에 이진수 자리수가 31이 될때까지 0을 채워주어 트라이에 저장하였다.

 

XOR연산의 최대값을 구하는 방법은 먼저 k의 이진수 앞 배열부터 비교해 가며 만약 해당 자리수 x 가 0일 때 cur에 1이 있으면 XOR이 True이므로 result에 1을 추가하고 cur['1']의 다음 노드로 간다. 만약 없다면 XOR이 False이므로 result에 0을 추가하고 cur['0']의 다음 노드로 간다. cur은 트라이의 마지막 깊이인 32가 아닌 이상 이어졌다는 뜻이므로 '0', 또는 '1'이 무조건 존재한다. x가 1일떄는 반대로 하면 된다.

 

여기서 최대값을 얻기 위해서 result에 '1'을 추가하는 것이 우선시되어야 하므로 x가 0일때, 1일떄 모두 result에 '1'이 추가되는 경우의 가능성 판별을 먼저 해 두었다. 이렇게 하면 현재 배열에서 만들 수 있는 XOR의 최대값을 구할 수 있다.

import sys

N=int(sys.stdin.readline().rstrip())

trie={}

def insert(val):
    cur = trie
    for x in val:
        if x not in cur:
            cur[x] = {}
        cur = cur[x]
    if '*' in cur:
        cur['*']+=1
    else:
        cur['*']=1

def delete(cur,depth):
    if depth==31:
        cur['*']-=1
        if cur['*'] == 0:
            del cur['*']
            if cur:
                return 0
            return 1
        else:
            return 0

    letter = binary[depth]
    nxt = delete(cur[letter],depth+1)
    
    if nxt==1:
        del cur[letter]
        if cur:
            return 0
        return 1
    return 0

def return_max(val):
    cur = trie
    result=str('')
    for x in val:
        if x=='0':
            if '1' in cur:
                result+='1'
                cur = cur['1']
                continue
            else:
                result+='0'
                cur = cur['0']
                continue
        else:
            if '0' in cur:
                result+='1'
                cur = cur['0']
                continue
            else:
                result+='0'
                cur = cur['1']
                continue
    return result

insert('0'.zfill(31))

for _ in range(N):
    a,b= map(int,sys.stdin.readline().rstrip().split())
    binary = format(b,'b').zfill(31)
    if a==1:
        insert(binary)
    elif a==2:
        delete(trie,0)
    else:
        print(int((return_max(binary)),2))

insert() 함수는 는 기존의 트라이에서 몇번 다루었던 방식과 같게 했고, delete() 함수는 DFS방식을 사용하여 최대 깊이에서 부터 제거를 계속하는 return 1, 제거를 멈추는 return 0을 반환한다. 만약 '*'이 줄어서 0이 되었으면 return 1 해준다. 그렇게 계속해서 제거하는 와중에 만약 cur에 값이 남아있다면 해당 cur은 다른 원소를 저장하는 경로가 포함되는 노드라는 뜻이므로 제거를 멈추는 return 0을 반환해가며 delete()함수를 만들었다.

 

시간 복잡도는 쿼리의 개수 M, 입력되는 x의 최대 범위를 N이라고 할 때 N을 이진수로 변환하고 (L = log2(N)), 이를 트라이 구조로 찾기에 (O(L)) 총 시간 복잡도는 O(MlogN) 으로 마칠 수 있다. 이번에는 시간 복잡도를 트라이로 줄이는 것이 저번 쿼리 문제들 처럼 신기하고 재미있는 문제였다.