[LeetCode] 421 | Maximum XOR of Two Numbers in an Array | Python

---

문제 링크: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

---

문제

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

---

조건

• 1 <= nums.length <= 2 * $10^5$
• 0 <= nums[i] <= $2^{31}$ - 1

---

내 풀이

Trie 구조를 사용한다.

Trie 구조란 문자열을 효과적으로 searching할 때 사용하는, 아래 그림과 같은 구조다.

'aaaa', 'aabc', 'abcd'의 세 문자열을 Trie 구조를 사용해서 저장하면 아래와 같이 표현된다.

XOR이 최대가 되기 위해서는 이진수로 표현했을 때, 각 자리수가 전부 다를 때 용이하다.

(ex. 0001 ^ 0000 = 0001, 0001 ^ 1111 = 1110)

이 문제를 풀기 위해서는 주어진 nums에 들어있는 모든 숫자를 이진수로 변환한 후 Trie에 저장한다.

Trie를 이용해 현재 수(num)를 이진수로 표현했을 때, XOR이 최대가 되어야하므로 반대의 길로 진행한다. (말로 표현하기 어려우니 아래 그림 참조)

'0101'이 입력으로 들어왔을 때, 각 자리수 별로 일치하지 않는 곳으로 내려가서 만나는 숫자가 XOR이 최대가 되는 수이다.

---

코드

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        trie = {}
        
        for num in nums:
            node = trie
            
            for i in range(31, -1, -1):
                bit = (num >> i) & 1
                
                if bit not in node:
                    node[bit] = {}
                node = node[bit]
            
            node['$'] = num
        
        ans = 0
        for num in nums:
            node = trie
            
            for i in range(31, -1, -1):
                bit = (num >> i) & 1
                
                if (1-bit) in node:
                    node = node[1-bit]
                else:
                    node = node[bit]
            
            ans = max(ans, num^node['$'])
        
        return ans