문제 개요
양의 정수로 이루어진 배열 arr과 쿼리 배열 queries가 주어진다고 가정해 봅시다. 각 쿼리는 queries[i] = [Li, Ri] 형태이며, 매 쿼리마다 인덱스 Li부터 Ri까지의 모든 요소를 XOR 연산한 값(즉, arr[Li] XOR arr[Li+1] XOR ... XOR arr[Ri])을 계산해야 합니다. 모든 쿼리의 결과를 담은 배열을 반환하는 것이 목표입니다.
예를 들어 입력 배열이 [1,3,4,8]이고 쿼리가 [[0,1],[1,2],[0,3],[3,3]]이라면, 결과는 [2,7,14,8]이 됩니다.
그 이유를 살펴보겠습니다. 배열 요소들의 이진수 표현은 다음과 같습니다.
- 1 = 0001
- 3 = 0011
- 4 = 0100
- 8 = 1000
따라서 각 쿼리의 XOR 결과는 아래와 같이 계산됩니다.
- [0,1]: 1 XOR 3 = 2
- [1,2]: 3 XOR 4 = 7
- [0,3]: 1 XOR 3 XOR 4 XOR 8 = 14
- [3,3]: 8
접근 방법: 접두사 XOR(Prefix XOR)
쿼리마다 구간을 일일이 순회하며 XOR을 계산하면 비효율적입니다. 대신 접두사 XOR 배열을 미리 만들어 두면 각 쿼리를 O(1) 시간에 처리할 수 있습니다. XOR 연산은 같은 값을 두 번 연산하면 0이 되는 성질(a XOR a = 0)을 가지므로, 구간 [L, R]의 XOR은 pre[R+1] XOR pre[L]로 손쉽게 구할 수 있습니다.
전체 해결 과정은 다음과 같습니다.
- n := arr의 크기
- 크기가 n+1인 배열 pre를 정의하고,
pre[i] := pre[i-1] XOR arr[i-1]로 채웁니다. - 결과를 저장할 배열 ans를 정의합니다.
- 각 쿼리 i에 대해 다음을 수행합니다.
- l := queries[i][0], r := queries[i][1]
- l과 r을 각각 1씩 증가시킵니다.
pre[r] XOR pre[l-1]값을 ans에 추가합니다.
- ans를 반환합니다.
C++ 구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
int n = arr.size();
vector <int> pre(n + 1);
for(int i = 1; i <=n; i++){
pre[i] = pre[i - 1] ^ arr[i - 1];
}
vector <int> ans;
for(int i = 0; i < queries.size(); i++){
int l = queries[i][0];
int r = queries[i][1];
l++;
r++;
ans.push_back(pre[r] ^ pre[l - 1]);
}
return ans;
}
};
main(){
vector<int> v = {1,3,4,8};
vector<vector<int>> v1 = {{0,1},{1,2},{0,3},{3,3}};
Solution ob;
print_vector(ob.xorQueries(v, v1));
}
입력
[1,3,4,8]
[[0,1],[1,2],[0,3],[3,3]]
출력
[2,7,14,8]
복잡도 분석
접두사 XOR 배열을 구성하는 데 O(n)의 시간이 소요되며, 이후 각 쿼리는 O(1)에 처리됩니다. 따라서 전체 시간 복잡도는 O(n + q)(q는 쿼리 개수), 공간 복잡도는 O(n)입니다. 이 방식은 쿼리가 많아질수록 단순 순회 방식(O(n × q))에 비해 압도적으로 빠른 성능을 보여줍니다.