C++에서 엄격하게 증가하는 하위 배열 개수 계산하기

정수 요소로 이루어진 배열이 주어졌을 때, 먼저 배열에서 만들 수 있는 모든 하위 배열(subarray)을 구한 뒤, 각 하위 배열의 요소들이 엄격하게 증가하는 순서(strictly increasing order)를 이루는지 확인해야 합니다. 조건을 만족하는 하위 배열만 카운트하고, 그렇지 않은 하위 배열은 버립니다.

여기서 핵심 아이디어는 하위 배열의 앞쪽 두 요소(0번째와 1번째 위치)부터 이미 증가하지 않는다면, 더 이상 해당 하위 배열을 검사하지 않고 바로 중단하는 것입니다. 이를 통해 불필요한 연산을 줄일 수 있습니다.

예시

입력: int a[] = {1, 7, 5}

출력: 엄격하게 증가하는 하위 배열의 개수는 1

설명: 가능한 하위 배열은 {1, 7, 5}, {1, 7}, {7, 5}이며, 이 중 엄격하게 증가하는 순서를 이루는 배열은 {1, 7} 하나뿐입니다.

입력: int a[] = {1, 2, 7, 10}

출력: 엄격하게 증가하는 하위 배열의 개수는 6

설명: 가능한 하위 배열은 {1, 2}, {1, 2, 7}, {1, 2, 7, 10}, {2, 7}, {2, 7, 10}, {7, 10}이며, 이 경우에는 모든 하위 배열이 엄격하게 증가하는 순서를 이룹니다.

알고리즘 접근 방식

배열을 선언하고 요소를 입력받은 뒤, 배열과 그 길이를 countIncSubarrays(a, n) 함수에 전달하여 처리합니다.
함수 내부에서 결과를 저장할 카운트 변수(count)를 0으로 초기화합니다.
i를 0부터 배열 길이까지 반복하는 외부 루프를 시작합니다. 이는 하위 배열의 시작 지점을 의미합니다.
루프 내부에서 j를 i+1부터 배열 길이까지 반복하는 내부 루프를 시작합니다.
내부 루프 안에서 a[j]가 a[j-1]보다 큰지 확인하고, 조건을 만족하면 count를 1 증가시킵니다.
조건을 만족하지 않으면 증가 순서 검사에 실패한 것이므로 break로 내부 루프를 종료합니다.
main 함수에서 함수 호출의 결과값을 받아 최종 개수를 출력합니다.

이 알고리즘의 시간 복잡도는 이중 루프 구조 때문에 O(n²)이며, 추가 공간 없이 동작하므로 공간 복잡도는 O(1)입니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int countIncSubarrays(int a[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[j] > a[j - 1])
                count++;   // 증가 순서 유지 시 카운트 증가
            else
                break;     // 증가 순서가 깨지면 검사 중단
        }
    }
    return count;
}

int main() {
    int a[] = {1, 2, 7, 10};
    int n = sizeof(a) / sizeof(a[0]);

    int result = countIncSubarrays(a, n);
    cout << "엄격하게 증가하는 하위 배열의 개수는 " << result << endl;

    return 0;
}

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

출력

엄격하게 증가하는 하위 배열의 개수는 6