이 문제에서는 정수로 이루어진 배열이 주어지며, 우리의 과제는 배열에서 선택할 수 있는 모든 삼중항(triplet)의 XOR 연산 결과 중 최댓값을 찾는 것입니다.
문제 이해를 위한 예시
입력 − array = {5, 6, 1, 2}
출력 − 6
설명 −
가능한 모든 삼중항의 XOR 값:
5^6^1 = 2
5^6^2 = 1
5^1^2 = 6
6^1^2 = 5
위 결과에서 가장 큰 값은 6이므로, 정답은 6이 됩니다.
해결 접근 방법
1. 단순 무차별 대입 방식 (Brute Force)
가장 직관적인 방법은 가능한 모든 삼중항 조합에 대해 XOR 값을 계산한 뒤, 그중 최댓값을 출력하는 것입니다. 이 방식은 구현이 간단하지만 세 겹의 반복문을 사용하므로 시간 복잡도가 O(n³)이 되어, 배열의 크기가 매우 클 경우에는 비효율적입니다.
2. 효율적인 방식 — 집합(Set) 활용
최대 XOR 값을 더 빠르게 찾기 위해 다음과 같은 전략을 사용합니다.
- 먼저, 배열 내 모든 두 원소의 쌍(pair)에 대한 XOR 값을 계산하여 집합(set)에 저장합니다.
- 그다음, 집합에 저장된 각 값과 배열의 각 원소를 XOR 연산하여 얻을 수 있는 최댓값을 찾습니다.
이 방식은 두 단계의 반복만 필요하므로 시간 복잡도를 O(n²) 수준으로 줄일 수 있어, 원소 수가 많은 배열에서도 훨씬 효과적입니다.
예제 코드
아래 프로그램은 위 해결 방법의 동작 과정을 보여줍니다.
#include <bits/stdc++.h>
using namespace std;
int MaxTripletXor(int n, int a[]){
set<int> XORpair;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
XORpair.insert(a[i] ^ a[j]);
}
}
int maxXOR = 0;
for (auto i : XORpair) {
for (int j = 0; j < n; j++) {
maxXOR = max(maxXOR, i ^ a[j]);
}
}
return maxXOR;
}
int main(){
int matrix[] = {1, 2, 3, 5, 7};
int n = sizeof(matrix) / sizeof(matrix[0]);
cout<<"삼중항의 최대 XOR 합은 "<<MaxTripletXor(n, matrix);
return 0;
}
출력 결과
삼중항의 최대 XOR 합은 7
마무리
이처럼 모든 쌍의 XOR 값을 미리 집합에 저장해 두면, 세 번째 반복문 없이도 삼중항의 최대 XOR 값을 효율적으로 계산할 수 있습니다. 입력 배열의 크기가 커질수록 O(n²) 방식이 O(n³) 방식보다 성능 면에서 큰 이점을 제공한다는 점을 기억하시기 바랍니다.