C++에서 엄격하게 감소하는 하위 배열의 개수 찾기

문제 개요

배열 A가 주어졌을 때, 길이가 1보다 큰 엄격하게 감소하는(strictly decreasing) 연속 부분 배열(subarray)의 총 개수를 구하는 문제입니다. 여기서 '엄격하게 감소한다'는 것은 배열 내 모든 인접한 원소가 이전 원소보다 반드시 작아야 한다는 의미입니다.

예를 들어 A = [100, 3, 1, 15]라고 가정해 보겠습니다. 이때 만들어지는 감소 부분 배열은 다음과 같습니다.

[100, 3]
[100, 3, 1]
[3, 1]

따라서 정답은 3이 됩니다.

핵심 아이디어

배열 전체를 일일이 검사하는 대신, 최대로 연속해서 감소하는 구간(run)의 길이를 이용하면 효율적으로 해결할 수 있습니다.

길이가 l인 하나의 감소 구간 안에서 만들 수 있는 길이 2 이상의 감소 부분 배열의 개수는 조합 공식으로 계산됩니다.

l × (l − 1) / 2

즉, 구간 내에서 시작점과 끝점을 뽑는 서로 다른 두 위치의 조합(C(l, 2))이 곧 부분 배열의 개수와 같습니다. 따라서 알고리즘은 다음과 같이 동작합니다.

배열을 한 번 순회하면서 인접한 두 원소를 비교합니다.
다음 원소가 현재 원소보다 작으면 현재 감소 구간의 길이 l을 1 증가시킵니다.
감소하지 않는 지점을 만나면 지금까지 누적된 l에 대해 l(l−1)/2를 결과에 더하고, l을 1로 초기화합니다.
순회가 끝난 후에도 l > 1이면 마지막 감소 구간에 대한 값을 추가로 더해 줍니다.

이 방법은 각 원소를 한 번씩만 확인하므로 시간 복잡도는 O(n), 추가 메모리는 O(1)로 매우 효율적입니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int countSubarrays(int array[], int n) {
    int count = 0;
    int l = 1;
    for (int i = 0; i < n - 1; ++i) {
        if (array[i + 1] < array[i])
            l++;
        else {
            count += (((l - 1) * l) / 2);
            l = 1;
        }
    }
    if (l > 1)
        count += (((l - 1) * l) / 2);
    return count;
}
int main() {
    int A[] = { 100, 3, 1, 13, 8 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Number of decreasing subarrays: " << countSubarrays(A, n);
}

실행 결과

Number of decreasing subarrays: 4

결과 분석

입력 배열 A = [100, 3, 1, 13, 8]에는 두 개의 감소 구간이 존재합니다.

[100, 3, 1]: 길이가 3이므로 3×2/2 = 3개 → [100, 3], [100, 3, 1], [3, 1]
[13, 8]: 길이가 2이므로 2×1/2 = 1개 → [13, 8]

두 구간의 결과를 합하면 총 4개의 엄격하게 감소하는 부분 배열이 됩니다.