C++ 쿼리 문제: 주어진 인덱스 왼쪽의 0과 1 개수 구하기

배열과 여러 개의 쿼리가 주어졌을 때, 각 쿼리 인덱스를 기준으로 그 왼쪽에 있는 0과 1의 개수를 구하는 문제를 살펴보겠습니다. 예를 들면 다음과 같습니다.

Input: arr[ ] = { 0, 1, 1, 1, 0, 0, 0, 1, 0, 0}, queries[ ] = { 2, 4, 1, 0, 5 }
Output:
query 1: zeros = 1, ones = 1
query 2: zeros = 1, ones = 3
query 3: zeros = 1, ones = 0
query 4: zeros = 0, ones = 0
query 5: zeros = 2, ones = 3

Input: arr[ ] = { 0, 0, 1, 1, 1, 0, 1, 0, 0, 1 }, queries[ ] = { 3, 2, 6 }
Output:
query 1: zeros = 2, ones = 1
query 2: zeros = 2, ones = 0
query 3: zeros = 3, ones = 3

문제 해결 접근법

단순 접근법

가장 간단한 해결 방법은 쿼리로 주어진 인덱스까지 배열을 처음부터 순회하면서 각 요소를 확인하는 것입니다. 요소가 0이면 0 카운터를 1 증가시키고, 그렇지 않으면 1 카운터를 1 증가시킵니다.

예제

#include <bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
    int queries[] = { 2, 4, 1, 0, 5 };
    int qsize = sizeof(queries) / sizeof(queries[0]);
    int zeros=0, ones=0;
    // 각 쿼리를 실행하는 루프
    for(int i = 0; i<qsize; i++){
        // 0과 1의 개수 세기
        for(int j = 0; j<queries[i]; j++){
            if(nums[j]==0)
                zeros++;
            else
                ones++;
        }
        cout << "\nquery " << i+1 << ": zeros = " << zeros << ", ones = " << ones;
        zeros=0;
        ones=0;
    }
    return 0;
}

출력

query 1: zeros = 1, ones = 1
query 2: zeros = 2, ones = 2
query 3: zeros = 0, ones = 1
query 4: zeros = 0, ones = 0
query 5: zeros = 2, ones = 3

효율적인 접근법

앞서 살펴본 단순 접근법에서는 새로운 쿼리가 들어올 때마다 매번 0번 인덱스부터 0과 1의 개수를 다시 계산해야 했습니다. 쿼리 개수와 배열 크기가 커질수록 상당히 비효율적입니다.

더 나은 방법은 배열을 한 번만 순회하면서 각 인덱스 왼쪽에 있는 0과 1의 개수를 미리 계산해 저장해 두고, 쿼리가 들어오면 해당 인덱스에 저장된 값을 바로 반환하는 것입니다. 이는 누적 합(prefix sum) 기법과 같은 원리로, 전처리 이후에는 각 쿼리를 상수 시간에 처리할 수 있습니다.

예제

#include <bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
    int queries[] = { 2, 4, 1, 0, 5 };
    int n = sizeof(nums) / sizeof(nums[0]);
    int arr[n][2];
    int zeros = 0, ones = 0;
    // nums 배열을 순회하며 누적 개수를 저장
    for (int i = 0; i < n; i++) {
        // 현재 인덱스 왼쪽의 0과 1 개수를 arr에 저장
        arr[i][0] = zeros;
        arr[i][1] = ones;
        // 조건에 따라 카운터 증가
        if (nums[i]==0)
            zeros++;
        else
            ones++;
    }
    int qsize = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < qsize; i++)
        cout << "\nquery " << i+1 << ": zeros = " << arr[queries[i]][0] << ", ones = " << arr[queries[i]][1];
    return 0;
}

출력

query 1: zeros = 1, ones = 1
query 2: zeros = 2, ones = 2
query 3: zeros = 0, ones = 1
query 4: zeros = 0, ones = 0
query 5: zeros = 2, ones = 3

시간 복잡도 분석

단순 접근법: 쿼리 하나를 처리할 때 최대 O(N)의 시간이 걸리므로, Q개의 쿼리를 처리하는 데는 전체적으로 O(Q × N)의 시간 복잡도를 가집니다.

효율적인 접근법: 전처리에 O(N), 각 쿼리 처리에 O(1)이 걸리므로 전체 시간 복잡도는 O(N + Q)입니다. 대신 O(N) 크기의 추가 저장 공간이 필요합니다.

결론

이 튜토리얼에서는 주어진 배열에서 각 쿼리 인덱스 왼쪽에 있는 0과 1의 개수를 구하는 방법을 알아보았습니다. 매번 처음부터 세는 단순 접근법과, 누적 개수를 미리 계산해 두는 효율적인 접근법을 비교했으며, 두 방식 모두 C++ 코드로 구현해 보았습니다. 이러한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 도움이 되기를 바랍니다.