[BOJ 13505] 두 수 XOR

문제 출처 : https://www.acmicpc.net/problem/13505

 

문제 풀이 :

 

Trie 문제입니다.

 

각 수를 비트로 쪼갠뒤 비트가 0인지 1인지에 대해 판단을 하여 높은 자리 수 부터 Trie를 구성하시면 됩니다.

 

아래는 예제 1번을 간략하게 Trie로 구성한 그림입니다.

 

위의 그림은 간략히 그린 것이고 실제로는 31자리 부터 시작해야 합니다.

 

Trie를 구성했으면 이제 가장 큰 XOR 값을 구해야합니다.

XOR값이 가장 크기 위해서는 이러한 생각을 할 수 있습니다.

 

어떠한 수에 대해 Trie 에서 제일 큰 자릿수 부터 반대 비트를 찾아 내려 간다면 그 수에 대해 가장 큰 XOR값을 가진 수를 찾을수 있다!

 

위의 그림에 색깔펜으로 그린 부분이 위의 로직을 1과 2에 대해 실행했을때의 결과값을 나타냅니다.

저는 항상 모든 비트가 다른 수가 존재한다는 보장이 없으니 반대 비트에 대해 저장된 값이 존재하지 않는다면 같은 비트를 타고 가는 방식으로 하였습니다.