문제 개요
이 문제에서는 아래 두 가지 유형 중 하나로 구성된 Q개의 쿼리가 차례로 주어집니다.
유형 1 – 삽입 (1, i): 값이 i인 요소를 자료구조에 추가합니다.
유형 2 – findXOR (2, i): 자료구조에 저장된 모든 요소와 요소 i를 XOR 연산한 결과 중 최댓값을 찾습니다.
자료구조는 처음에 값 0을 가진 단 하나의 요소만 포함하는 상태로 시작합니다.
예제로 문제 이해하기
입력
Queries: (1, 9), (1, 3), (1, 7), (2, 8), (1, 5), (2, 12)
출력
15 15
설명
각 쿼리를 순서대로 처리하면,
(1, 9) => 자료구조 => {9}
(1, 3) => 자료구조 => {9, 3}
(1, 7) => 자료구조 => {9, 3, 7}
(2, 8) => 최대 XOR(_, 8) = 15, 즉 XOR(7, 8)
(1, 5) => 자료구조 => {9, 3, 7, 5}
(2, 12) => 최대 XOR(_, 12) = 15, 즉 XOR(3, 12)
해결 접근 방식
이 문제는 트라이(Trie) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 트라이는 검색에 널리 쓰이는 특수한 형태의 탐색 트리로, 여기서는 각 노드가 0과 1 두 개의 자식 노드를 갖도록 구성하여 숫자의 이진 표현을 저장합니다.
동작 방식은 다음과 같습니다.
- 삽입(유형 1): 새로 추가할 숫자를 32비트 이진수로 변환한 뒤, 최상위 비트부터 최하위 비트까지 순서대로 트라이에 삽입합니다.
- 최대 XOR 조회(유형 2): 주어진 숫자의 각 비트에 대해 반대 비트(0이면 1, 1이면 0)로 이어지는 자식 노드가 존재하는지 확인합니다. 반대 비트 경로가 있다면 해당 비트 위치의 XOR 결과가 1이 되므로 답에 그 비트 값을 더하고 해당 경로로 이동하고, 없다면 같은 비트 경로로 이동합니다. 32비트를 모두 순회하면 최대 XOR 값을 얻을 수 있습니다.
이 방식은 각 쿼리를 숫자의 비트 길이에 비례하는 시간, 즉 O(32) 안에 처리할 수 있어 대량의 쿼리에도 매우 효율적입니다.
C++ 구현 코드
#include<bits/stdc++.h>
using namespace std;
struct Trie {
Trie* children[2];
bool isLeaf;
};
bool check(int N, int i) {
return (bool)(N & (1<<i));
}
Trie* newNode() {
Trie* temp = new Trie;
temp->isLeaf = false;
temp->children[0] = NULL;
temp->children[1] = NULL;
return temp;
}
void insertVal(Trie* root, int x) {
Trie* val = root;
for (int i = 31; i >= 0; i--) {
int f = check(x, i);
if (! val->children[f])
val->children[f] = newNode();
val = val->children[f];
}
val->isLeaf = true;
}
int solveQueryType2(Trie *root, int x){
Trie* val = root;
int ans = 0;
for (int i = 31; i >= 0; i--) {
int f = check(x, i);
if ((val->children[f ^ 1])){
ans = ans + (1 << i);
val = val->children[f ^ 1];
}
else
val = val->children[f];
}
return ans;
}
void solveQueryType1(Trie *root, int x){
insertVal(root, x);
}
int main(){
int Q = 6;
int query[Q][2] = {{1, 9}, {1, 3}, {1, 7}, {2, 8}, {1, 5}, {2, 12}};
Trie* root = newNode();
for(int i = 0; i < Q; i++){
if(query[i][0] == 1 ){
solveQueryType1(root, query[i][1]);
cout<<"Value inserted to the data Structure. value =
"<<query[i][1]<<endl;
}
if(query[i][0] == 2){
cout<<"The maximum XOR with "<<query[i][1]<<" is
"<<solveQueryType2(root, query[i][1])<<endl;
}
}
return 0;
}
실행 결과
Value inserted to the data Structure. value = 9
Value inserted to the data Structure. value = 3
Value inserted to the data Structure. value = 7
The maximum XOR with 8 is 15
Value inserted to the data Structure. value = 5
The maximum XOR with 12 is 15
코드 핵심 요약
- check(N, i): 정수 N의 i번째 비트가 1인지 판별하는 헬퍼 함수입니다.
- insertVal(root, x): 숫자 x의 32비트를 트라이에 삽입하는 함수로, 유형 1 쿼리에서 호출됩니다.
- solveQueryType2(root, x): 트라이를 따라가며 x와의 최대 XOR 값을 계산해 반환하는 함수로, 유형 2 쿼리에서 호출됩니다.