Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 배열에서 두 숫자의 최대 XOR 값 구하기 (이진 트라이 활용)

문제 개요

비어 있지 않은 숫자 배열 a₀, a₁, a₂, …, aₙ₋₁이 주어졌을 때(단, 0 ≤ aᵢ < 2³¹), 0 ≤ i, j < n 조건을 만족하는 aᵢ XOR aⱼ 값 중 최댓값을 구하는 것이 목표입니다.

예를 들어 입력 배열이 [3, 10, 5, 25, 2, 8]이라면 출력은 28이 됩니다. 이는 5 XOR 25 = 28이 만들 수 있는 가장 큰 값이기 때문입니다.

모든 쌍을 일일이 비교하는 방법은 O(n²)의 시간이 걸리지만, 이진 트라이(Binary Trie) 자료구조를 활용하면 O(n × 32) 시간 복잡도로 훨씬 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 각 숫자를 32비트 이진수로 보고 트라이에 삽입합니다.
  • 각 숫자에 대해 XOR 결과를 최대화하려면 현재 비트와 반대되는(다른) 비트를 가진 경로를 따라가야 합니다.
  • 상위 비트일수록 결과에 미치는 영향이 크므로, 높은 자릿수부터 반대 비트를 우선 선택하는 그리디 방식으로 탐색합니다.

알고리즘 접근 방식

  1. insertNode() 함수를 정의합니다. val과 head를 인자로 받습니다.
    • curr := head로 초기화합니다.
    • i를 31부터 0까지 반복합니다:
      • bit := (val >> i) AND 1 — val의 i번째 비트를 추출합니다.
      • curr의 child[bit]가 null이면 새 노드를 생성합니다.
      • curr := curr의 child[bit]로 이동합니다.
  2. find() 함수를 정의합니다. val과 head를 입력으로 받습니다.
    • curr := head, ans := 0으로 초기화합니다.
    • i를 31부터 0까지 반복합니다:
      • bit := (val >> i) AND 1
      • curr의 child[!bit], 즉 현재 비트와 반대 방향 자식이 존재하면 ans에 해당 비트를 설정(ans |= (1 << i))하고 그 노드로 이동합니다.
      • 반대 방향 자식이 없으면 child[bit]로 이동합니다.
    • ans를 반환합니다.
  3. 메인 메서드에서 다음을 수행합니다:
    • ans := 0, n := nums의 크기, head := 새 노드를 준비합니다.
    • 배열의 모든 원소를 insertNode()로 트라이에 삽입합니다.
    • 각 원소에 대해 find()를 호출한 뒤 ans를 최댓값으로 갱신합니다.
    • ans를 반환합니다.

C++ 구현 예시

아래 코드를 통해 동작 방식을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
struct Node{
    Node* child[2];
    Node(){
        child[1] = child[0] = NULL;
    }
};
class Solution {
    public:
    void insertNode(int val, Node* head){
        Node* curr = head;
        for(int i = 31; i>= 0; i--){
            int bit = (val >> i) & 1;
            if(!curr->child[bit]){
                curr->child[bit] = new Node();
            }
            curr = curr->child[bit];
        }
    }
    int find(int val, Node* head){
        Node* curr = head;
        int ans = 0;
        for(int i = 31; i>= 0; i--){
            int bit = (val >> i) & 1;
            if(curr->child[!bit]){
                ans |= (1 << i);
                curr = curr->child[!bit];
            } else {
                curr = curr->child[bit];
            }
        }
        return ans;
    }
    int findMaximumXOR(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        Node* head = new Node();
        for(int i = 0; i < n; i++){
            insertNode(nums[i], head);
        }
        for(int i = 0; i < n; i++){
            ans = max(ans, find(nums[i], head));
        }
        return ans;
    }
};
main(){
    vector<int> v = {3,10,5,25,2,8};
    Solution ob;
    cout << (ob.findMaximumXOR(v));
}

입력

[3,10,5,25,2,8]

출력

28

복잡도 분석

각 숫자마다 32비트를 한 번씩 처리하므로 시간 복잡도는 O(n × 32), 즉 사실상 선형 시간입니다. 공간 복잡도 역시 트라이의 최대 깊이가 32이므로 O(n × 32)입니다. 완전탐색의 O(n²)에 비해 대규모 입력에서도 빠르게 동작한다는 점이 이 접근법의 가장 큰 장점입니다.