이번에 Leetcode 문제를 풀다 충격적 Solution을 봐서 정리하려 글을 남긴다.
먼저 문제이다.
문제는 정말 간단하다. 숫자 List가 주어지면 그 중 2개로 가장 큰 XOR 결과를 반환하면 된다.
이 문제가 속한 파트는 Trie라서 처음에 Trie로 풀어보려 했다.
Example 대상으로 풀리긴 한다. 다만 Submit하면 TLE(Time Limit Error)가 뜬다.
Python이 워낙 느리기도 하고 최적화도 잘 못해서 그런 것 같았다.
기존 코드
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word, val):
curr = self.root
for i in range(len(word)):
bit = word[i]
if bit not in curr.children:
curr.children[bit] = TrieNode()
curr = curr.children[bit]
curr.isEnd = True
curr.value = val
def search(self, word, target):
curr = self.root
for i in range(len(word)):
bit = word[i]
if bit == '1' and curr.children.get('0'):
curr = curr.children['0']
elif bit == '0' and curr.children.get('1'):
curr = curr.children['1']
elif curr.children.get(bit):
curr = curr.children[bit]
else:
break
return target^curr.value
class TrieNode:
def __init__(self):
self.children = {}
self.isEnd = False
self.value = 0
class Solution(object):
def findMaximumXOR(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
self.trie = Trie()
max_xor = -2**(32)
for i in nums:
binary_string = (bin(i)[2:]).zfill(31)
self.trie.insert(binary_string, i)
max_xor = max(max_xor, self.trie.search(binary_string, i))
return max_xor내 코드 아이디어에 Solution에서 본 내용을 토대로 최대한 최적화도 했다.
(순수 내 아이디어만 해도 example 정답은 나왔지만 TLE가 떴다. 혹시나 하는 마음에 최대한 해봤지만... 역시 TLE가 나왔다..)
먼저 내 아이디어는 정말 간단하다. 예를 들어 10101(b)가 있다고 치자. (b)는 binary(이진수)라는 뜻이다.
이 숫자와 XOR해서 최대화하려면 어떻게 해야 할까? 바로 01010(b)일 것이다.
XOR은 비트가 다를 때 1, 같으면 0이 나오는 연산자이다.
따라서 주어진 숫자의 각 자릿수마다 정 반대의 비트를 가지는 숫자가 XOR 연산을 최대로 만들 것이다.
그래서 각 숫자들을 먼저 Trie에 넣는다. 1-0-1-0-1 이렇게.
그리고 다 넣은 다음, 이제 찾는다.
만일 Input이 1-0-1-0-1이라 치자. 첫 자리부터 찾는 것이다.
첫 자리는 1이니 0을 찾고, 만일 없다면 어쩔 수 없이 1로 간다.
이 과정을 반복한다.
+) 왜 하필 첫 자리부터 찾아야 할까? 이진법 특성 상 첫 자리가 큰 게 압도적이기 때문이다.
1000(b), 0111(b) 중 큰 것은 당연히 전자다.
그래서 최종적으로 나온 숫자와 XOR 연산을 하고 max를 통해 최댓값을 갱신한다.
시간 복잡도는 O(N*L)(N : 숫자 개수, L : 숫자 길이, 여기서는 32)이다.
충분히 할만하다고 생각했는데... 아니였다.
Discuss - Solution 코드
이제부터 정말 충격적이었다.
아니 이게 왜 충격적이야? 하는 사람들이 있을 수 있지만
비트 연산자를 거의 접해보지 못한 나에게 이렇게 깔끔하게 짠 코드는 충격이었다.
def findMaximumXOR(self, nums):
answer = 0
for i in range(32)[::-1]:
answer <<= 1
prefixes = {num >> i for num in nums}
answer += any(answer^1 ^ p in prefixes for p in prefixes)
return answer일단 길이부터 말이 안되고(6줄..ㅋㅋ), 내용 역시 함축적으로 쓰다보니 어려워졌다.
파인만 테크닉(최대한 쉽게 풀어서 설명해야 이해한 것이다)을 사용해서 이해해보자.
[초기 세팅]
먼저 초기에 answer(반환값)을 0으로 둔다.
[반복문]
for i in range(32)[::-1]
range(32)는 [0, 1, ... 31]의 리스트를 만든다.
[::-1]은 리스트의 순서를 뒤집는다.
따라서 [31, 30, ... , 1, 0]이 된다.
즉 i는 31, 30.. 순서로 나오는 것이다.
answer <<= 1
이 말은 answer를 좌측으로 한 번 민다는 것이다.
예를 들어 answer가 101(b)라면 1010(b)로 만드는 것이다.
prefixes = {num >> i for num in nums}
nums 배열(기존에 주어진 숫자 배열)의 숫자들을 우측으로 i 만큼 민다.
nums가 [3, 4, 5], i가 1이라면
[3, 4, 5]는 곧 [10(b), 11(b), 100(b)]이므로 [1(b), 1(b), 10(b)]가 된다.
자 여기서 핵심 파트가 나온다.
answer += any(answer^1 ^ p in prefixes for p in prefixes)
좀 어려울 수 있다. 차근차근 보자(사실 나는 종이에 계속 쓰면서 이해했다..).
먼저 그 전에, XOR 연산자의 2가지 특징을 이해해야 한다.
첫 번째, XOR의 항등원은 0이다.
이게 대체 무슨 말일까. 숫자 2를 생각해보자. 2는 10(b)이다.
2^2 = 10(b)^10(b) = 00 = 0이다. 즉 같은 숫자를 XOR 하면 0이 나온다.
반대로 2^0 = 2이다. 즉 어떤 숫자에 0을 XOR 하면 그대로 나온다.
두 번째, 만일 a와 b가 완벽한 XOR 짝이라면, a^b^a = b이다.
사실 이 역시 간단하다.
a를 1010, b를 0101이라 두자.(편의상 (b)는 생략했다)
a^b는 당연히 1111이다. 가정을 완벽한 XOR 짝이라 했으니..
a^b^a는 1111^a = 0101 = b이다.
즉 짝이 맞는다면 서로 생성되는 관계이다!(적절한 단어가 없어 생각나는 대로 적는다)
자... 이제 슬슬 감이 오는가?
당연히 오지 않는다. 나 역시 한참을 끙끙거렸다.
answer^1 ^ p in prefixes for p in prefixes 이 조건은 곧
answer^1^p 가 prefix 안에 있고, p 역시 prefix라면.. 이라는 뜻이다.
answer^1^p를 q라 두자. q는 prefix 안에 있다.
그렇다면 answer^1^p = q이다.
여기서 양쪽에 ^p를 해보자.
answer^1^p^p = q^p
짜잔! answer^1 = p^q(XOR은 당연히 교환된다.. 순서가 중요한 것이 아니기에) 라는 식이 나온다.
즉 만일 저 조건이 성립한다면 answer^1인 p, q가 prefix안에 있다는 말이다.
헉, 그치만 아직 답까지는 멀어보인다.
당연하다. 이 6줄에 너무 많은 내용이 함축되어 있다.
괜찮다. 차근차근하자.
이 문제에서 풀이하는 방식은, XOR 최댓값을 앞자리부터 찾아 뒤로 연장하는 것이다.
자 만약 우리가 가장 큰 7자리 bit(앞에서부터!)를 찾았다고 치자.
문자열 총 길이는 모르겠고, 그냥 일단 앞에서부터 찾은 최대 7자리를 말하는 것이다.
그러면 최대 8자리는 뭘까?
바로 최대 7자리에서 마지막 뒤에 하나 붙인 것이다.
이는 이진수의 특성(1000이 0111보다 큰 것)을 기반으로 한다.
그렇다면 마지막 뒤에 하나는 뭘 붙여야 할까? 앞에서 7자리 찾은 것처럼 똑같이 하면 된다!
자자자... 한 번 보자.
prefixes = {num >> i for num in nums} ... (1)
answer += any(answer^1 ^ p in prefixes for p in prefixes) ... (2)편의상 (1), (2)로 표시하겠다.
(1)은 무슨 말이냐, 앞서 i를 31, 30.. 으로 설정해둔 것 기억나는가?
즉 num을 우측으로 31칸 민다는 것이다.
num은 최대 31자리이다. 왜냐? Input 제한이 2^32-1 이라서 그렇다.
2^32는 100...0인 32자리이다. 그거보다 1 작다면 0111...1 인 1이 31개인 숫자다.
011...1을 우측으로 31칸 밀어보자. 01을 우측으로 1칸 밀면 0이다.
즉 01...1을 우측으로 31칸 밀면 0이다.(i가 31이라면 사실 무조건 0이다)
prefixes는 {0, 0,...0}이 된다.
파이썬에서 중괄호('{')는 set, 즉 집합을 의미한다.
따라서 prefixes는 최종적으로 {0}이 된다.
(2)를 보자. any 함수는 이 조건을 만족하는게 하나라도 있다면 True(1), 아니면 False(0)을 반환한다.
즉 저 코드는 if ~~ : answer +=1 랑 같은 말이다.
아하! 앞서 말한 p^q가 answer^1을 만족하면 1을 더해주란 말이구나!!
이제 슬슬 감이 잡힐 것이다.
answer은 반복문에서 <<1 연산자를 통해 한 칸 왼쪽으로 밀리고 0이 추가되었다.
예를 들어 이전 정답이 1011이라 하자, p, q는 각각 1010, 0010이다.
이제 반복문이 돌았다. answer는 10110이 되었다.
케이스는 2개이다.
1) p^q = answer^1인 경우.
answer^1이 10111이므로 p, q가 10100, 00101이면 될 것이다.(다른 경우도 가능)
이 경우에 p^q가 10111을 만든다!
기존 최댓값이 10110이므로 += any 함수를 통해 10111로 만든다.
최댓값을 1 갱신하는 것이다.
2) p^q != answer^1인 경우.
answer^1이 10111이지만 p, q가 10100, 00100이라면 XOR 결과가 같지 않다.
즉 기존 최댓값 10110 그대로 간다.
하지만! Prefixes는 전체 숫자를 다 담았기에 p, q가 무수히 많이 존재할 수 있다.
그래서 반복적으로 체크..체크... 하면서 가능한 경우를 제외하는 것이다.
answer가 좌측으로 1칸씩 밀릴 때 마다 경우는 줄어들테니..
+) 보충 설명
위의 경우에서 prefixes가 {10100, 00101, 00100}이었다. 각각 20, 5, 4이다.
answer가 1011일때(prefixes가 한 칸 짧았을 때, 즉 {1010, 0010}일 때)는 저 세 숫자 모두 가능했다. 즉 20, 5, 4 모두 후보군이다(가능한 경우 : 20^5, 20^4).
근데 Prefixes는 set이니 중복 숫자는 합쳐져서 보인다. Bucket 생각해보면 된다.
이제 answer 길이가 한 칸 늘어났다. 후보군 중 20 ^ 5는 answer^1과 같지만 20^4는 같지 않다(애초에 5^4는 고려 대상이 아니다, 이전 레벨에서 멈췄다).
즉 후보가 20, 5로 줄어든 것이다. 이렇게 줄여나간다!
이 코드의 목적은 풀어서 설명하면 다음과 같다.
- 이전 정답(1자리 짧은거)을 만드는 p, q가 있는지 체크
- 갱신할 마지막 자리에서 opposite bit를 가지고 있는지 체크
마지막에 그 최댓값을 반환한다.
정말 아름다운 코드이다.
코드가 어려워서 한땀한땀 풀어적었다.
최대한 쉽게 설명하려 했는데 잘 이해될 지 모르겠다..
어느순간 번쩍!! 하면서 이해가 될 것이다.
추후에 다시 볼 일이 생길 것 같아 스스로 이해용으로 적었다.
C++이었다면... Trie...에서... 끝났을...텐데.. ㅠㅠㅠ
