C++로 배열 구간의 합을 0으로 만들 수 있는지 확인하는 쿼리 처리 방법

문제 소개

n개의 요소로 이루어진 배열 A가 있고, 각 요소의 값은 -1 또는 1입니다. 여기에 m개의 구간 쿼리 Q가 주어지며, 각 쿼리는 Q[i] = (li, ri) 형태입니다. 배열 A의 요소들을 자유롭게 재배열할 수 있을 때, li번째부터 ri번째까지 구간의 합을 정확히 0으로 만들 수 있다면 해당 쿼리의 답은 1, 만들 수 없다면 0입니다. 목표는 모든 쿼리에 대한 답을 효율적으로 구하는 것입니다.

예를 들어 입력이 A = [-1, 1, 1, 1, -1], Q = [[1, 1], [2, 3], [3, 5], [2, 5], [1, 5]]라면 출력은 [0, 1, 0, 1, 0]이 됩니다.

핵심 아이디어

이 문제의 열쇠는 "재배열"이라는 조건입니다. 배열 전체의 순서를 마음대로 바꿀 수 있기 때문에, 특정 구간에 어떤 요소들을 배치할지 사실상 우리가 선택할 수 있습니다. 따라서 구간 [l, r]의 합을 0으로 만들 수 있는지는 다음 두 가지 조건만으로 판단할 수 있습니다.

구간 길이가 짝수여야 합니다. 합이 0이 되려면 +1과 -1의 개수가 정확히 같아야 하므로, 구간에 포함되는 요소의 개수는 반드시 짝수여야 합니다.
필요한 만큼의 +1과 -1이 배열에 존재해야 합니다. 길이가 L인 구간의 합을 0으로 만들려면 +1이 L/2개, -1이 L/2개 필요합니다. 즉, 배열 전체에서 -1의 개수와 1의 개수가 각각 L/2 이상이어야 합니다.

이를 위해 먼저 배열에서 음수(-1)의 개수를 센 뒤, 음수 개수와 양수 개수 중 더 작은 값을 z로 설정합니다. 이후 각 쿼리마다 위 두 조건만 확인하면 됩니다.

알고리즘 단계

배열 A를 순회하며 음수(-1)의 개수를 세어 z에 저장합니다.
z가 양수(1)의 개수(n − z)보다 크다면 z를 n − z로 바꿉니다. 결과적으로 z = min(음수 개수, 양수 개수)가 됩니다.
각 쿼리 (l, r)에 대해 다음을 확인합니다.
- (r − l)이 홀수인지 → 구간 길이(r − l + 1)가 짝수인지 검사
- (r − l + 1) / 2 ≤ z 인지 → 필요한 +1/-1 쌍의 개수가 충분한지 검사
두 조건을 모두 만족하면 1, 그렇지 않으면 0을 출력합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A, vector<vector<int>> Q) {
    int n = A.size();
    int m = Q.size();
    int z = 0;

    // 배열에서 -1의 개수를 셉니다
    for (int i = 0; i < n; ++i)
        z += (A[i] < 0);

    // z를 음수 개수와 양수 개수 중 작은 값으로 맞춥니다
    if (z > n - z)
        z = n - z;

    // 각 쿼리를 상수 시간에 처리합니다
    for (int i = 0; i < m; i++) {
        int l = Q[i][0];
        int r = Q[i][1];
        bool ok = ((r - l) % 2 == 1) && ((r - l + 1) / 2 <= z);
        cout << (ok ? 1 : 0) << ", ";
    }
}

int main() {
    vector<int> A = { -1, 1, 1, 1, -1 };
    vector<vector<int>> Q = { { 1, 1 }, { 2, 3 }, { 3, 5 }, { 2, 5 }, { 1, 5 } };
    solve(A, Q);
    return 0;
}

입력

A = { -1, 1, 1, 1, -1 }
Q = { { 1, 1 }, { 2, 3 }, { 3, 5 }, { 2, 5 }, { 1, 5 } }

출력

0, 1, 0, 1, 0,

결과 검증

예제 배열에는 -1이 2개, 1이 3개 있으므로 z = min(2, 3) = 2입니다. 각 쿼리를 살펴보면 다음과 같습니다.

[1, 1]: 구간 길이가 1로 홀수 → 0
[2, 3]: 구간 길이가 2이고 필요한 쌍 1개 ≤ 2 → 1
[3, 5]: 구간 길이가 3으로 홀수 → 0
[2, 5]: 구간 길이가 4이고 필요한 쌍 2개 ≤ 2 → 1
[1, 5]: 구간 길이가 5로 홀수 → 0

시간 복잡도

배열을 한 번 순회하는 데 O(n)이 걸리고, 각 쿼리는 상수 시간에 처리되므로 전체 시간 복잡도는 O(n + m)입니다. 추가 배열 없이 O(1)의 공간만 사용하는 매우 효율적인 방법입니다.