C++로 주어진 범위 내 합을 가지는 부분 배열 개수 구하기

문제 소개

이 글에서는 C++ 프로그래밍으로 주어진 범위 내에 합이 포함되는 부분 배열(subarray)의 개수를 구하는 문제를 해결합니다. 양의 정수로 이루어진 배열 arr[]와 범위 {L, R}가 주어졌을 때, 합이 L부터 R 사이에 속하는 모든 부분 배열의 총 개수를 계산해야 합니다.

다음은 문제를 이해하기 위한 간단한 예시입니다.

입력 : arr[] = {1, 4, 6}, L = 3, R = 8

출력 : 3

해당하는 부분 배열은 {1, 4}, {4}, {6}입니다.


입력 : arr[] = {2, 3, 5, 8}, L = 4, R = 13

출력 : 6

해당하는 부분 배열은 {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}입니다.

문제 해결 접근 방법

이 문제를 C++로 해결하는 두 가지 방법을 살펴보겠습니다.

1. 브루트 포스(Brute Force) 접근법

가장 기본적인 브루트 포스 방식은 모든 부분 배열의 합을 하나씩 계산한 뒤, 그 합이 주어진 범위 내에 존재하는지 확인하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(n²)(n은 배열의 크기)이므로, 배열이 커질수록 많은 시간이 소요된다는 단점이 있습니다.

2. 효율적인 접근법 (슬라iding 윈도우)

시간을 절약하기 위해 슬라이딩 윈도우(Sliding Window) 기법을 활용한 효율적인 방법을 사용할 수 있습니다. 이 기법을 적용하면 O(n)의 시간 복잡도로 훨씬 빠르게 결과를 계산할 수 있습니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;
int subCount(int *arr, int n, int x){
    int start = 0, end = 0, sum = 0, count = 0;
    while (end < n){ // 이 반복문에서 오른쪽 경계를 이동합니다
        sum = sum + arr[end];
        while(start <= end && sum >= x){ // 이 반복문은 왼쪽 경계를 이동합니다
            sum = sum - arr[start]; // 왼쪽 경계를 이동하며 합을 감소시킵니다.
                                    // 이전 요소들을 제외하기 위함입니다.
            start++;                // 왼쪽 경계를 이동합니다.
        }
        count = count + ((end - start) + 1); // 부분 배열의 개수를 셉니다.
        end++;
    }
    return count;
}
int main(){
    int arr[] = { 1, 4, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int L = 3;
    int R = 8;
    int answer;
    answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // 최종 답안.
    cout << answer << "\n";
    return 0;
}

실행 결과

코드 설명

이 접근법에서는 먼저 subCount 함수를 사용해 합이 주어진 범위의 상한(R)보다 작은 부분 배열의 개수를 세고, 여기서 합이 하한(L)보다 작은 부분 배열의 개수를 빼줍니다. 그 결과가 바로 합이 [L, R] 범위에 속하는 부분 배열의 최종 개수입니다.

subCount 함수 동작 원리

subCount 함수는 슬라이딩 윈도우 기법을 활용해 합이 x보다 작은 부분 배열의 개수를 찾습니다.

처음에는 start와 end 값을 모두 0으로 초기화합니다. 배열을 순회하는 동안 start부터 end까지의 요소 합을 유지합니다. 만약 합이 x보다 크거나 같아지면, start를 앞으로 이동시키면서 해당 요소를 합에서 빼줍니다. 이 과정은 합이 x보다 작아지거나 start가 end보다 커질 때까지 반복됩니다.

그런 다음 현재 윈도우에서 만들 수 있는 부분 배열의 개수인 (end - start) + 1만큼 count를 증가시키고, 오른쪽 경계(end)를 1 증가시킵니다. 외부 반복문이 종료되면 지금까지 누적된 부분 배열의 총 개수를 반환합니다.

마무리

이 글에서는 슬라이딩 윈도우 기법을 활용해 주어진 범위 내의 합을 가지는 부분 배열의 개수를 O(n) 시간 복잡도로 구하는 문제를 해결했습니다. 또한 C++ 프로그램과 함께 일반적인 방법(브루트 포스)과 효율적인 방법 두 가지 접근 방식을 모두 학습했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다.