정수 요소로 이루어진 배열 arr[]와 변수 k가 주어졌을 때, 최댓값이 k보다 큰 부분 배열(subarray)의 개수를 구하는 것이 목표입니다. 예를 들어 배열이 [1, 2, 3]이고 k가 1이라면, 만들 수 있는 부분 배열은 [1], [2], [3], [1,2], [2,3], [1,2,3]으로 총 6개입니다. 이 가운데 최댓값이 1보다 큰 부분 배열은 [2], [3], [1,2], [2,3], [1,2,3]의 5개이므로 정답은 5가 됩니다.
예제로 이해하기
입력 − arr[] = {1, 2, 5, 3}, k = 3
출력 − 최댓값이 k보다 큰 부분 배열의 개수: 6
설명 − 가능한 모든 부분 배열은 [1], [2], [5], [3], [1,2], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3]입니다. 이 중 최댓값이 3보다 큰 배열은 5를 포함하는 것들로, 다음과 같습니다.
[5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3]
따라서 총 6개의 부분 배열이 해당됩니다.
입력 − arr[] = {1, 2, 3, 4, 5}, k = 4
출력 − 최댓값이 k보다 큰 부분 배열의 개수: 5
설명 − 4보다 큰 요소는 5 하나뿐입니다. 따라서 5를 포함하는 부분 배열은 다음과 같습니다.
[5], [4,5], [3,4,5], [2,3,4,5], [1,2,3,4,5]
따라서 총 5개의 부분 배열이 해당됩니다.
알고리즘의 접근 방식
이 방식의 핵심은 길이가 n인 배열의 전체 부분 배열 개수가 n*(n+1)/2라는 사실입니다. 역으로 생각하여, 최댓값이 k보다 크지 않은(즉 모든 요소가 k 이하인) 부분 배열의 개수를 센 뒤 전체 개수에서 빼면 됩니다. 이를 위해 k보다 큰 요소는 건너뛰고, 모든 요소가 k 이하로 이루어진 연속 구간의 길이를 셉니다. 길이가 l인 구간은 l*(l+1)/2개의 부분 배열을 만들 수 있으므로, 각 구간마다 이 값을 더해 그 합을 X라고 합시다. 최종적으로 n*(n+1)/2에서 X를 빼면 원하는 결과를 얻을 수 있습니다.
- 정수 배열 arr[]와 변수 k를 입력으로 받습니다.
- 함수 maximum_k(int arr[], int size, int k)는 배열, k, 배열의 길이를 인자로 받아 최댓값이 k보다 큰 부분 배열의 개수를 반환합니다.
- count를 0으로 초기화합니다.
- while 루프를 사용해 인덱스 i=0부터 i<size까지 배열을 순회합니다.
- arr[i]>k인 요소는 continue 문으로 건너뜁니다.
- 그렇지 않으면 내부 while 루프를 시작해 해당 구간의 길이를 셉니다.
- arr[i]<=k이고 i<size인 동안 i와 temp(k 이하 요소로만 이루어진 구간의 길이)를 증가시킵니다.
- 내부 while 루프가 끝나면 현재 구간의 길이가 temp에 저장되며, temp*(temp+1)/2를 계산해 count에 더합니다.
- 이 과정을 나머지 모든 구간에 대해 반복합니다.
- 외부 while 루프가 끝나면 count에는 모든 요소가 k 이하인 부분 배열의 총 개수가 저장됩니다.
- 전체 부분 배열 개수인 size*(size+1)/2에서 count를 빼서 count를 갱신합니다.
- 갱신된 count를 결과로 반환합니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 메모리 없이 동작한다는 장점이 있습니다.
예제
#include <bits/stdc++.h>
using namespace std;
int maximum_k(int arr[], int size, int k){
int count = 0;
int i = 0;
while (i < size){
if (arr[i] > k){
i++;
continue;
}
int temp = 0;
while (i < size && arr[i] <= k){
i++;
temp++;
}
int temp_2 = temp * (temp + 1);
count = count + temp_2 / 2;
}
count = (size * (size + 1) / 2 - count);
return count;
}
int main(){
int arr[] = { 4, 1, 2, 7, 8, 3 };
int k = 5;
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays whose maximum element is greater than k are: "<<maximum_k(arr, size, k);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of subarrays whose maximum element is greater than k are: 14
결과를 검증해 보면, 배열 {4, 1, 2, 7, 8, 3}의 전체 부분 배열 개수는 6×7/2 = 21개입니다. 여기서 7과 8은 k=5보다 크므로, 모든 요소가 5 이하인 구간은 [4, 1, 2](길이 3, 부분 배열 6개)와 [3](길이 1, 부분 배열 1개)뿐입니다. 따라서 21 − (6 + 1) = 14가 정답이 됩니다.