서로 다른 두 수의 최대 XOR 값
자바스크립트 코딩테스트 문제로 bit-trie 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
배열에서 서로 다른 두 수를 골라 만들 수 있는 XOR 값의 최댓값을 구하는 문제입니다.
문제 설명
0 이상의 정수로 이루어진 배열 nums가 주어집니다.
서로 다른 두 인덱스 i, j를 골라 nums[i] ^ nums[j]를 계산했을 때, 만들 수 있는 값들 중 가장 큰 값을 반환하는 maxPairXorValue 함수를 작성하세요.
여기서 ^는 JavaScript의 비트 XOR 연산자입니다.
제한사항
2 <= nums.length <= 1000000 <= nums[i] <= 2^20- 반드시 서로 다른 두 인덱스를 골라야 합니다.
- 같은 값이 여러 번 등장하면 서로 다른 원소로 사용할 수 있습니다.
예시
- 입력:
nums = [3, 10, 5, 25, 2, 8]→ 출력:28 - 입력:
nums = [0, 0, 0, 0]→ 출력:0 - 입력:
nums = [8, 1, 2, 15]→ 출력:14
힌트
- XOR 값은 높은 비트부터 1이 되는지가 더 중요합니다.
- 어떤 수와 가장 큰 XOR을 만들고 싶다면, 현재 비트에서는 가능하면 반대 비트를 만나고 싶습니다.
- 숫자를 이진수 경로처럼 저장하는 자료구조를 떠올려 보세요.
해설
이 문제를 모든 두 수 쌍으로 검사하면 O(n^2)이 걸려 입력이 큰 경우 부담이 큽니다.
핵심은 XOR의 큰 자리 비트를 먼저 1로 만드는 선택이 항상 유리하다는 점입니다.
1. 이진 트라이 만들기
각 숫자를 비트열로 보고, 가장 높은 비트부터 차례대로 0 또는 1 자식으로 내려가는 이진 트라이에 넣습니다.
예를 들어 숫자 5는 이진수로 00101처럼 볼 수 있고, 각 비트가 트라이의 한 단계가 됩니다.
2. 현재 수와 가장 잘 맞는 상대 찾기
어떤 수 x와 XOR 값을 크게 만들려면,
x의 현재 비트가0이면 가능하면1쪽으로x의 현재 비트가1이면 가능하면0쪽으로
내려가는 것이 좋습니다.
이렇게 하면 그 자리 XOR 결과가 1이 되어 더 큰 값을 만들 수 있습니다.
반대 비트가 없을 때만 같은 비트 쪽으로 내려갑니다.
3. 왜 탐욕이 맞을까?
XOR 결과는 이진수 크기 비교를 따르므로, 더 높은 자리에서 1을 만드는 것이 낮은 자리 여러 개를 바꾸는 것보다 항상 더 중요합니다.
그래서 매 비트마다 가능하면 반대 비트를 선택하는 탐욕이 전체 최적해로 이어집니다.
4. 진행 방식
- 모든 수를 트라이에 넣습니다.
- 각 수마다 트라이를 다시 내려가며 만들 수 있는 최대 XOR 값을 계산합니다.
- 그중 최댓값을 답으로 사용합니다.
5. 예시로 보기
nums = [3, 10, 5, 25, 2, 8]일 때,
5는 25와 짝을 이루면 5 ^ 25 = 28이 됩니다.
5 = 00101
25 = 11001
XOR= 11100 = 28
트라이를 따라 내려가면 높은 비트부터 가능한 한 반대 비트를 고르면서 이 값을 찾아낼 수 있습니다.
이 방식의 시간 복잡도는 비트 수를 B라고 할 때 O(n * B)입니다. 이 문제에서는 B가 작게 고정되어 있어 충분히 빠릅니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.