C++ 두 배열 간 요소별 최대 XOR 값 구하기

문제 개요

이 문제에서는 n개의 원소를 가진 두 배열 A와 B가 주어집니다. 우리가 해야 할 일은 배열 A의 모든 원소에 대해 배열 B와의 최대 가능한 XOR 값을 구하는 프로그램을 작성하는 것입니다.

즉, 배열 A의 각 원소마다 배열 B에서 XOR 결과가 가장 커지는 원소를 하나씩 선택해 그 값을 출력해야 합니다.

문제 이해를 위한 예시

입력 −

array A = {3, 6, 11, 9}
array B = {8, 2, 4, 1}

출력 −

11 14 15 13

설명 −

배열 A의 각 원소와 배열 B의 모든 원소를 XOR 연산한 결과를 살펴보고, 각 원소별로 최댓값을 선택해 보겠습니다.

3 XOR 8 = 11, 3 XOR 2 = 1, 3 XOR 4 = 7, 3 XOR 1 = 2 → 최댓값 = 11
6 XOR 8 = 14, 6 XOR 2 = 4, 6 XOR 4 = 2, 6 XOR 1 = 1 → 최댓값 = 14
11 XOR 8 = 3, 11 XOR 2 = 9, 11 XOR 4 = 15, 11 XOR 1 = 10 → 최댓값 = 15
9 XOR 8 = 1, 9 XOR 2 = 11, 9 XOR 4 = 13, 9 XOR 1 = 8 → 최댓값 = 13

단순한 접근 방식과 한계

위 예시처럼 모든 조합을 일일이 계산해 최대 XOR 값을 찾는 단순한(naive) 방법도 있습니다. 하지만 이 방식은 두 개의 중첩 반복문을 사용하기 때문에 시간 복잡도가 O(n²)에 달해 효율적이지 못합니다.

따라서 더 나은 해결 방법이 필요합니다.

트라이(Trie) 자료구조를 활용한 효율적인 접근

더 효율적인 방법은 트라이(trie) 자료구조를 활용하는 것입니다. 배열 B의 모든 원소를 이진수 형태로 트라이에 미리 저장해 둔 뒤, 배열 A의 원소와 비교하여 최대 XOR 값을 찾습니다.

배열 A의 특정 원소에 대해서는 최상위 비트(MSB)부터 차례로 확인하면서, XOR 결과에서 해당 비트가 1이 되도록 반대되는 비트 경로를 따라 내려갑니다. 이 과정을 다음 MSB까지 반복하면 배열 B에서 해당 원소와의 XOR 값이 최대가 되는 원소를 찾을 수 있습니다.

이 방식은 각 원소당 비트 수(32비트)만큼만 탐색하므로 전체 시간 복잡도가 O(n·log(max))로 줄어들어, 단순 이중 반복문 방식보다 훨씬 빠릅니다.

예제 코드

다음은 배열 A의 모든 원소에 대해 배열 B와의 최대 가능한 XOR 값을 구하는 C++ 프로그램입니다.

#include<iostream>
using namespace std;
struct trie{
    int value;
    trie *child[2];
};
trie * get(){
    trie * root = new trie;
    root -> value = 0;
    root -> child[0] = NULL;
    root -> child[1] = NULL;
    return root;
}
void insert(trie * root, int key){
    trie * temp = root;
    for (int i = 31; i >= 0; i--){
        bool current_bit = key & (1 << i);
        if (temp -> child[current_bit] == NULL)
            temp -> child[current_bit] = get();
        temp = temp -> child[current_bit];
    }
    temp -> value = key;
}
int findMaxXor(trie * root, int element){
    trie * temp = root;
    for (int i = 31; i >= 0; i--){
        bool bits = ( element & ( 1 << i) );
        if (temp -> child[1 - bits] != NULL)
            temp = temp -> child[1 - bits];
        else
            temp = temp -> child[bits];
    }
    return (element ^ temp -> value);
}
int main(){
    int A[] = {3, 11, 6, 9};
    int B[] = {8, 2, 4, 1};
    int N = sizeof(A)/sizeof(A[0]);
    trie * root = get();
    for (int i = 0; i < N; i++)
    insert(root, B[i]);
    cout<<"The maximum possible XOR of every possible element in array A with Array B is\n";
    for (int i = 0; i < N; i++)
    cout <<findMaxXor(root, A[i])<<"\t";
    return 0;
}

코드 설명

insert 함수: 배열 B의 각 원소를 32비트 이진수로 변환하여 트라이에 삽입합니다.
findMaxXor 함수: 배열 A의 원소에 대해 상위 비트부터 확인하며, XOR 결과가 1이 되도록 반대 비트 경로가 존재하면 그 경로를 따르고, 없으면 같은 비트 경로를 따릅니다.
탐색이 끝난 리프 노드에 저장된 값과 원래 원소를 XOR 연산하여 최댓값을 반환합니다.

출력 결과

The maximum possible XOR of every possible element in array A with Array B is
11 15 14 13