문제 설명
정수 배열 arr가 주어졌을 때, 세 개의 인덱스 i, j, k를 선택한다고 가정해 봅시다. 이때 인덱스는 다음 조건을 만족해야 합니다.
(0 <= i < j <= k < N) — 여기서 N은 배열의 크기입니다.
각 값은 아래와 같이 정의됩니다.
- a = arr[i] XOR arr[i + 1] XOR ... XOR arr[j - 1]
- b = arr[j] XOR arr[j + 1] XOR ... XOR arr[k]
우리가 구해야 하는 것은 a와 b의 값이 서로 같은 삼중항 (i, j, k)의 개수입니다.
예를 들어 입력이 [2, 3, 1, 6, 7]이라면 출력은 4가 됩니다. 조건을 만족하는 삼중항은 (0, 1, 2), (0, 2, 2), (2, 3, 4), (2, 4, 4)입니다.
해결 접근 방법
이 문제는 해시 맵(map)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 인덱스 j를 기준점으로 삼아, 왼쪽 구간([i, j-1])에서 만들 수 있는 모든 XOR 값을 미리 맵에 저장해 두고, 오른쪽 구간([j, k])의 XOR 값과 일치하는 경우의 수를 누적하는 것입니다.
알고리즘을 단계별로 살펴보면 다음과 같습니다.
- 결과값 ret := 0으로 초기화하고, n := 배열의 크기로 설정합니다.
- i를 1부터 n-1까지 반복하면서 각 기준 위치마다 다음을 수행합니다.
- XOR 빈도를 저장할 맵 m을 하나 정의합니다.
- x1 := 0, x2 := 0으로 초기화합니다.
- j를 i - 1부터 0까지 감소시키며 반복합니다. 각 단계에서 x1에 arr[j]를 XOR 연산한 뒤, 맵의 m[x1] 값을 1씩 증가시킵니다.
- j를 i부터 n - 1까지 증가시키며 반복합니다. 각 단계에서 x2에 arr[j]를 XOR 연산한 뒤, ret에 m[x2] 값을 더합니다.
- 모든 반복이 끝나면 ret을 반환합니다.
이 방식은 왼쪽 부분 배열의 XOR 값과 오른쪽 부분 배열의 XOR 값이 일치하는 모든 조합을 놓치지 않고 셀 수 있게 해줍니다.
구현 예제
더 나은 이해를 위해 다음 C++ 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countTriplets(vector<int>& arr) {
int ret = 0;
int n = arr.size();
for (int i = 1; i < n; i++) {
map<int, int> m;
int x1 = 0;
int x2 = 0;
for (int j = i - 1; j >= 0; j--) {
x1 = x1 ^ arr[j];
m[x1]++;
}
for (int j = i; j < n; j++) {
x2 = x2 ^ arr[j];
ret += m[x2];
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,3,1,6,7};
cout << (ob.countTriplets(v));
}입력
{2,3,1,6,7}출력
4
복잡도 분석
각 기준 인덱스 i마다 왼쪽과 오른쪽 구간을 한 번씩 순회하므로 시간 복잡도는 O(n²)입니다(맵 연산으로 인한 로그 계수가 추가될 수 있습니다). 공간 복잡도는 맵에 최대 n개의 XOR 값을 저장하므로 O(n)입니다. 성능이 중요하다면 std::map 대신 std::unordered_map을 사용하여 평균적으로 더 빠른 조회 속도를 얻을 수 있습니다.