문제 개요
n개의 원소로 이루어진 배열이 주어졌을 때, 배열의 원소들을 순서대로 사용해 만들 수 있는 모든 부분 배열(subarray)의 XOR 값을 구하고, 그 결과들을 다시 한 번 XOR 연산한 최종 값을 출력하는 것이 이 문제의 목표입니다.
예제를 통해 문제를 살펴보겠습니다.
- 입력 − array = {1, 3, 6, 8}
- 출력 − 0
- 설명 − 아래처럼 가능한 모든 부분 배열의 XOR을 계산한 후, 그 값들을 다시 XOR합니다.
(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6) ^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)
효율적인 접근 방법
가장 단순한 해결책은 모든 부분 배열을 하나씩 순회하며 각각의 XOR을 직접 계산하는 것입니다. 하지만 이 방법은 부분 배열의 개수가 O(n²)개이고 각각을 합산하는 데 추가 비용이 들어 매우 비효율적입니다.
더 나은 접근 방식은 각 원소가 전체 부분 배열 목록에서 몇 번 등장하는지 그 빈도를 계산하는 것입니다. 여기서 XOR의 핵심 성질을 활용할 수 있습니다.
같은 값이 짝수 번 XOR되면 그 결과는 반드시 0이다.
이 성질 덕분에 짝수 번 등장하는 원소는 최종 결과에 영향을 주지 않으므로 완전히 무시할 수 있습니다. 즉, 홀수 번 등장하는 원소들만 XOR하면 곧바로 최종 답을 얻을 수 있습니다.
등장 빈도 계산 공식
인덱스 i에 있는 원소가 포함되는 부분 배열의 개수는 시작 지점의 선택지 (i+1)개와 끝 지점의 선택지 (n-i)개의 곱으로 구할 수 있습니다.
빈도 = (i + 1) * (n - i)
배열 {1, 3, 6, 8}에 이 공식을 적용하면 다음과 같습니다.
- 인덱스 0 (값 1): 1 × 4 = 4회 → 짝수 → 제외
- 인덱스 1 (값 3): 2 × 3 = 6회 → 짝수 → 제외
- 인덱스 2 (값 6): 3 × 2 = 6회 → 짝수 → 제외
- 인덱스 3 (값 8): 4 × 1 = 4회 → 짝수 → 제외
모든 원소가 짝수 번 등장하므로 최종 XOR 결과는 0이 됩니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int xorSubarrayXors(int arr[], int N){
int result = 0;
for (int i = 0; i < N; i++){
int frequency = (i + 1) * (N - i);
if (frequency % 2 == 1)
result ^= arr[i];
}
return result;
}
int main() {
int arr[] = {1, 3, 6, 8};
int N = sizeof(arr) / sizeof(arr[0]);
cout << "모든 부분 배열 XOR 값들의 XOR : " << xorSubarrayXors(arr, N);
return 0;
}실행 결과
모든 부분 배열 XOR 값들의 XOR : 0
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 결과를 저장할 변수 외에 추가 메모리를 사용하지 않아 공간 복잡도는 O(1)입니다. 모든 부분 배열을 일일이 계산하는 브루트포스 방식(O(n³))에 비해 훨씬 효율적이라는 점이 이 풀이의 가장 큰 장점입니다.