정수로 이루어진 배열 arr[]와 숫자 K가 주어집니다. 목표는 배열의 모든 요소가 K보다 큰 부분 배열(subarray)의 개수를 구하는 것입니다. 예를 들어 배열이 [1, 2, 3]이고 K가 1이라면, 조건을 만족하는 부분 배열은 [2], [3], [2, 3]입니다.
예제로 이해하기
입력 − arr[] = { 2, 2, 1, 1, 1, 5 }; K=1
출력 − 모든 요소가 K보다 큰 부분 배열의 개수: 4
설명 − 조건을 만족하는 부분 배열은 [2], [2], [5], [2, 2]입니다. 각 부분 배열의 모든 요소가 1보다 큽니다.
입력 − arr[] = { 3, 4, 5, 6 }; K=2
출력 − 모든 요소가 K보다 큰 부분 배열의 개수: 10
설명 − 가능한 부분 배열은 [3], [4], [5], [6], [3, 4], [4, 5], [5, 6], [3, 4, 5], [4, 5, 6], [3, 4, 5, 6]이며, 총 개수는 10개입니다.
풀이 접근 방식
for 반복문을 사용해 배열을 순회하면서 다음 규칙을 적용합니다. 현재 요소가 K보다 크면 카운트(count)를 증가시키고, 그렇지 않으면 지금까지 쌓인 연속된 요소들로 만들 수 있는 부분 배열의 개수인 count × (count + 1) / 2를 결과에 더한 뒤 count를 0으로 초기화합니다. 순회가 끝난 후 count가 0이 아니라면 마지막 구간에 대한 count × (count + 1) / 2를 한 번 더 더해줍니다.
숫자 배열
arr[]를 입력받습니다.함수
sub_greater_k(int arr[], int size, int k)는 배열과 그 크기, 기준값 k를 받아 모든 요소가 k보다 큰 부분 배열의 개수를 반환합니다.count를 0으로 초기화합니다.
i = 0부터 i < size까지 for 반복문으로 배열을 순회합니다.
arr[i] > k이면 count를 증가시킵니다.
k보다 큰 요소가 count개 연속되면 만들 수 있는 부분 배열은 count × (count + 1) / 2개이므로, 이 값을 총합(total)에 더하고 count를 0으로 초기화합니다.
반복문 종료 후 count가 0이 아니라면 count × (count + 1) / 2를 총합에 추가합니다.
총합(total)을 결과로 반환합니다.
이 방법은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 효율적으로 문제를 해결할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int sub_greater_k(int arr[], int size, int k){
int count = 0;
int total = 0;
for (int i = 0; i < size; i++){
if (arr[i] > k){
count++;
}
else{
total += (count) * (count + 1) / 2;
count = 0;
}
}
if(count){
total += (count) * (count + 1) / 2;
}
return total;
}
int main(){
int arr[] = {2, 4, 6, 1, 3, 7, 9 };
int size = sizeof(arr) / sizeof(arr[0]);
int k = 7;
cout<<"모든 요소가 K보다 큰 부분 배열의 개수: "<<sub_greater_k(arr, size, k);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
모든 요소가 K보다 큰 부분 배열의 개수: 1