백준[13505] 두 수 XOR (Python3)

XOR 연산으로도 풀 수 있지만, 트라이로 풀었다.

 

XOR 연산이 1과 0으로 이루어지기 때문에, 각 수들을 이진수로 변환한 값들을 트라이로 만들어주면 된다.
편의상 최대 자릿수를 구한 다음, 이 길이에 맞춰 다른 이진수들에 padding 값으로 0을 붙였다.
이걸 안 해주니 탐색 코드에서 이진수 자릿수까지 검증해야 해서 불편했다.

 

탐색 과정은 다음과 같다.

1. 현재 자릿수와 반전되는 수가 노드에 있는지 본다. (1이면 0, 0이면 1)
2. 있다면 임시 배열에 1 추가. 아니면 0 추가
3. 임시 배열에 있는 값으로 십진수 변환

코드

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, S):
        current_node = self.root
        for s in S:
            if s not in current_node:
                current_node[s] = {}
            current_node = current_node[s]
        current_node[-1] = True

    def search(self, S):
        current_node = self.root
        nums = []
        for s in S:
            if s == 1:
                find = 0
            else:
                find = 1
            if find in current_node:
                nums.append(1)
                current_node = current_node[find]
            else:
                nums.append(0)
                current_node = current_node[s]
        ret = 0
        for i, num in enumerate(nums):
            if num > 0:
                ret += 2 ** (len(S) - i - 1)
        return ret

def main():
    trie = Trie()
    N = int(input())
    nums = list(map(int, input().split()))
    nums.sort(reverse=True)
    binaries = []
    maxLen = 0
    for i, num in enumerate(nums):
        temp = (bin(num)[2:])
        nums[i] = temp
        maxLen = max(maxLen, len(temp))
    for i, num in enumerate(nums):
        gap = maxLen - len(num)
        if gap > 0:
            temp = "0" * gap + num
            nums[i] = temp
        temp = list(map(int, nums[i]))
        trie.insert(temp)
        binaries.append(temp)

    answer = 0
    for binary in binaries:
        answer = max(answer, trie.search(binary))
    print(answer)


if __name__ == "__main__":
    main()