문제

[백준] 두 수 XOR (Platinum 3)

요약

N(2 <= N <= 100,000)개의 수가 주어졌을 때, XOR한 값이 가장 큰 서로 다른 두 수를 찾아라. 중복된 수가 주어질 수 있다.

분류

  • 트라이
  • 그리디 알고리즘

풀이

1. 내 풀이 (트라이, 그리디)

  • XOR한 값의 큰 자리부터 1이 될 수록 유리하다. 이진수로 변환했을 때, 가장 길이가 긴 숫자는 반드시 가장 큰 자리가 1이다. 따라서 그보다 2 이상 작은 수와 XOR 연산을 하면 첫 자리는 반드시 1이 된다.(그리디)
  • 트라이를 이용해 탐색 시간을 O(log2(N))으로 줄였다.
import sys
input = sys.stdin.readline

n = int(input())
arr = list(set(map(int, input().split())))
arr.sort(reverse=True)
m = bin(max(arr))[2:]
l = len(m)


class TrieNode:
    def __init__(self):
        self.left = None  # 0
        self.right = None  # 1


root = TrieNode()

for num in arr:
    t = root
    target = "0" * (l + 2 - len(bin(num))) + bin(num)[2:]

    for tar in target:
        if tar == "0":
            if t.left is None:
                t.left = TrieNode()
            t = t.left
        elif tar == "1":
            if t.right is None:
                t.right = TrieNode()
            t = t.right

ans = -1
for tar in arr:
    t = root
    t_ans = ""
    t_n = bin(tar)[2:]
    if len(t_n) != l:
        break
    for num in t_n:
        if num == "0":
            if t.right is None:
                t = t.left
                t_ans += "0"
            else:
                t = t.right
                t_ans += "1"
        elif num == "1":
            if t.left is None:
                t = t.right
                t_ans += "0"
            else:
                t = t.left
                t_ans += "1"

    ans = max(ans, int(t_ans, 2))

print(ans)