Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 해결하는 모든 부분 배열의 XOR의 XOR 범위 쿼리 문제

이 글에서는 주어진 범위 내에 존재하는 모든 부분 배열(subarray)의 XOR 값을 계산하여 출력하는 방법을 다룹니다. 먼저 예시를 통해 문제를 이해해 보겠습니다.

문제 예시

입력 : arr[] = { 4, 1, 2, 3, 5 }, Q = 3

쿼리

q1 = { 1, 2 }
q2 = { 2, 4 }
q3 = { 1, 4 }

출력 : 0
2
0

쿼리 2(범위 2~4)를 예로 들어 설명하면, 해당 범위에서 만들 수 있는 부분 배열은 다음과 같습니다.

{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}

여기서 각 원소가 등장하는 횟수를 세어 보면 다음과 같습니다.

  • 1은 3번 등장
  • 2는 4번 등장
  • 3은 3번 등장

XOR의 중요한 성질 중 하나는 짝수 번 등장하는 값은 서로 상쇄되어 사라진다는 것입니다. 따라서 4번 등장한 2는 상쇄되고, 홀수 번 등장한 1과 3만 남아 그 둘의 XOR인 2가 최종 답이 됩니다.

이처럼 이 문제는 규칙성을 파악한 뒤, 그 패턴에 맞게 구현하는 것이 핵심입니다.

해결 접근 방법

이 문제의 핵심은 범위 안에 숨어 있는 패턴을 찾아내는 것입니다. 패턴을 발견하면 이를 코드로 구현하고 결과를 검증하면 됩니다.

관찰해야 할 두 가지 핵심 규칙은 다음과 같습니다.

  1. 범위의 크기가 짝수인 경우: 모든 부분 배열을 나열했을 때 각 원소가 짝수 번씩 등장하므로, 전체 XOR은 반드시 0이 됩니다.
  2. 범위의 크기가 홀수인 경우: 홀수 번 등장하는 원소들은 범위 내에서 짝수 위치에 있는 원소들입니다. 따라서 답은 범위 내 짝수 위치 원소들의 XOR과 같습니다.

이를 빠르게 처리하기 위해 짝수 인덱스용 접두사 XOR 배열(prefeven)과 홀수 인덱스용 접두사 XOR 배열(prefodd), 두 개의 접두사 배열을 미리 만들어 둡니다. 쿼리가 들어오면 왼쪽 끝 l이 짝수인지 홀수인지만 확인하고 적절한 접두사 배열을 사용해 O(1) 시간에 답을 구할 수 있습니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
void ansQueries(int prefeven[], int prefodd[], int l, int r){
    if ((r - l + 1) % 2 == 0) // 범위 내 원소 개수가 짝수인 경우
        cout << "0";
    else{
        if (l % 2 == 0) // l이 짝수인 경우
            cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
        else // l이 홀수인 경우
            cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
    }
}
int main(){
    int arr[] = {4, 1, 2, 3, 5};
    int n = sizeof(arr) / sizeof(int); // 배열의 크기
    int l[] = {1, 2, 1}; // 쿼리의 왼쪽 인덱스
    int r[] = {2, 4, 4}; // 쿼리의 오른쪽 인덱스
    int q = sizeof(l) / sizeof(int); // 쿼리의 개수
    int prefodd[n] = {0}, prefeven[n] = {0}; // 짝수/홀수 인덱스별 접두사 XOR
    for (int i = 1; i <= n; i++){
        if ((i) % 2 == 0){ // i가 짝수이면 prefeven 갱신
            prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
            prefodd[i] = prefodd[i - 1];
        }else{
            prefeven[i] = prefeven[i - 1];
            prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
        }
    }
    for (int i = 0; i < q; i++){
        ansQueries(prefeven, prefodd, l[i], r[i]);
    }
    return 0;
}

실행 결과

0
2
0

코드 동작 원리 상세 설명

이 접근법의 논리를 단계별로 정리하면 다음과 같습니다.

1. 범위 크기가 짝수일 때
범위 [l, r]의 크기가 짝수라면, 모든 부분 배열을 나열했을 때 각 원소가 정확히 짝수 번 등장합니다. XOR 연산에서 짝수 번 등장한 값은 모두 상쇄되므로 답은 무조건 0입니다.

2. 범위 크기가 홀수일 때
범위의 크기가 홀수라면 홀수 번 등장하는 원소들이 존재하며, 이들은 범위 내에서 짝수 위치에 있는 원소들입니다. 따라서 답은 범위 내 짝수 위치 원소들의 XOR 값이 됩니다.

3. 접두사 배열 활용
prefeven 배열에는 짝수 인덱스 원소들의 누적 XOR을, prefodd 배열에는 홀수 인덱스 원소들의 누적 XOR을 저장합니다. 쿼리를 처리할 때는 l이 짝수인지 홀수인지 확인한 후, 해당 접두사 배열에서 (r번째 값) XOR (l-1번째 값)을 계산하면 범위 내 짝수 위치 원소들의 XOR을 즉시 얻을 수 있습니다.

이 방식으로 각 쿼리를 O(1) 시간 복잡도에 처리할 수 있으며, 전체 시간 복잡도는 전처리에 O(N), 쿼리 처리에 O(Q)입니다.

마무리

이 튜토리얼에서는 모든 부분 배열의 XOR의 XOR에 대한 범위 쿼리 문제를 해결했습니다. 문제의 패턴을 관찰하고, 짝수/홀수 인덱스별 접두사 XOR 배열을 활용하는 C++ 프로그램과 전체 풀이 과정을 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 문제 해결에 도움이 되기를 바랍니다.