[백준/python] 13505 두 수 XOR

def make_bin(num):
    tmp = bin(num)[2:]
    return tmp.zfill(max_length)


def insert(num):
    binary = make_bin(num)

    now = trie
    for b in binary:
        now = now.setdefault(int(b), dict())


def compare(num):
    now = trie

    binary = make_bin(num)
    res = ""
    for b in binary:

        check = 1-int(b)
        
        if check in now:
            res+= "1"
            now = now[check]

        else:
            res+= "0"
            now = now[1-check]
    
    return int(res,2)


trie = dict()

N = int(input())
arr = [*map(int,input().split())]

max_length = len(bin(max(arr)))-2

for num in arr:
    insert(num)

ans = 0
for num in arr:
    ans = max(ans, compare(num))

print(ans)

이진수를 트라이 구조로 저장한다는 발상이 신기한 트라이 응용문제입니다. 트라이 구조를 활용해 저장하고, 최대치를 탐색하면 일반적인 탐색에 비해 효율이 높습니다.

트라이

간단히 딕셔너리로 트라이구조를 구현했습니다.

그 후, compare 함수를 통해 해당 위치의 trie에 반대되는 이진수가 있는 경우 1을 더하여 내려가는 방식으로 구현했습니다.

최대 길이를 미리 구해두어 zfill메서드를 통해 길이을 동일하게 만들었습니다. 이를 통해, 자리수가 차이나는 숫자 간에도 추가적인 예외처리 없이 비교할 수 있습니다.

마지막으로, compare함수를 모든 숫자에 적용해보며 ans의 최대값을 찾아 출력합니다.