양의 정수로 이루어진 배열 arr[]가 주어졌을 때, 길이가 1 이상인 모든 부분 배열 중 증가하지 않는(non-increasing) 부분 배열의 개수를 구하는 것이 목표입니다. 여기서 '증가하지 않는'이란 각 원소가 바로 앞의 원소보다 크지 않다는 의미, 즉 앞 원소 ≥ 뒤 원소의 관계가 성립함을 뜻합니다.
예를 들어 arr[] = {1, 3, 2}라면 조건을 만족하는 부분 배열은 {1}, {2}, {3}, {3, 2}의 4개입니다.
예시
입력
arr[] = {5, 4, 4, 5}
출력
증가하지 않는 부분 배열의 개수: 7
설명
{5}, {4}, {4}, {5}, {5, 4}, {4, 4}, {5, 4, 4}
입력
arr[] = {10, 9, 8, 7}
출력
증가하지 않는 부분 배열의 개수: 10
설명
{10}, {9}, {8}, {7}, {10, 9}, {9, 8}, {8, 7}, {10, 9, 8}, {9, 8, 7}, {10, 9, 8, 7}
값이 감소하거나 같게 이어지는 구간에서는 그 안의 모든 부분 배열이 조건을 만족하므로, 길이가 n인 구간에서는 n × (n + 1) ÷ 2개의 부분 배열을 한 번에 셀 수 있습니다.
접근 방법
핵심 아이디어는 다음과 같습니다. 인덱스 i부터 이어지는 원소들이 증가하지 않는 상태를 유지하는 동안에는 구간을 계속 늘려갈 수 있지만, 중간에 arr[j] > arr[j − 1]인 지점이 나타나는 순간 그 이후 구간은 더 이상 증가하지 않는 배열일 수 없습니다. 따라서 증가하지 않는 구간의 길이를 temp라고 할 때, 해당 구간에서 만들어지는 부분 배열의 개수인 temp × (temp + 1) ÷ 2를 정답에 더하고, 새로운 구간의 길이를 1로 초기화한 뒤 탐색을 이어가면 됩니다.
알고리즘 단계
- 배열 arr[]와 그 크기를 받아 개수를 반환하는 함수 subarrays(int arr[], int size)를 정의합니다.
- count는 0, 현재 구간의 길이 temp는 1로 초기화합니다.
- for 반복문으로 배열을 순회하며, arr[i + 1] ≤ arr[i]이면 구간이 아직 증가하지 않는 상태이므로 temp를 1 증가시킵니다.
- 그렇지 않고 arr[i + 1] > arr[i]라면 구간이 끊긴 것이므로, 지금까지 구간에서 만들 수 있는 부분 배열의 수 (temp × (temp + 1)) ÷ 2를 count에 더하고 temp를 1로 되돌립니다.
- 모든 순회가 끝난 뒤에는 마지막 구간에 대해 (temp × (temp + 1)) ÷ 2를 count에 한 번 더 더해 줍니다.
- count를 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int subarrays(int arr[], int size){
int count = 0;
int temp = 1;
for(int i = 0; i < size - 1; ++i){
if (arr[i + 1] <= arr[i]){
temp++;
} else {
count += ((temp + 1) * temp) / 2;
temp = 1;
}
}
count += ((temp + 1) * temp) / 2;
return count;
}
int main(){
int arr[] = {2, 6, 1, 8, 3};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "증가하지 않는 부분 배열의 개수: " << subarrays(arr, size);
return 0;
}
실행 결과
증가하지 않는 부분 배열의 개수: 7
위 코드에서 배열 {2, 6, 1, 8, 3}의 증가하지 않는 부분 배열은 {2}, {6}, {1}, {8}, {3}, {6, 1}, {8, 3}으로 총 7개입니다.
복잡도 분석
배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.