정수 배열 arr와 두 개의 정수 k, threshold가 주어졌을 때, 크기가 k이고 평균이 임계값(threshold)보다 크거나 같은 부분 배열(sub-array)의 개수를 구하는 문제입니다.
예를 들어, 입력이 다음과 같다고 가정해 보겠습니다.
- arr = [2,2,2,2,5,5,5,8]
- k = 3
- threshold = 4
이 경우 출력은 3이 됩니다. 조건을 만족하는 부분 배열은 [2,5,5], [5,5,5], [5,5,8]이며, 각각의 평균은 4, 5, 6으로 모두 임계값 4 이상이기 때문입니다.
문제 해결 접근 방법
이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 매번 새로운 부분 배열의 합을 계산하는 대신, 윈도우가 한 칸 이동할 때 앞쪽 요소는 빼고 뒤쪽 요소는 더하는 방식으로 합을 갱신합니다.
알고리즘 단계
- sum := 0, div := k, n := 배열의 요소 개수로 초기화합니다.
- 배열의 첫 k개 요소의 합을 sum에 저장합니다.
- 결과를 담을 변수 ret := 0으로 초기화합니다.
- i := 0부터 시작하고 j는 k부터 n-1까지, i와 j를 동시에 1씩 증가시키며 반복합니다.
- 만약 sum / div >= threshold라면 ret을 1 증가시킵니다.
- sum에서 arr[i]를 빼고(윈도우 왼쪽 제거), arr[j]를 더합니다(윈도우 오른쪽 추가).
- 반복이 끝난 후 마지막 윈도우에 대해서도 sum / div >= threshold인지 확인하여 ret을 증가시킵니다.
- ret을 반환합니다.
C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
double sum = 0;
double div = k;
int n = arr.size();
for(int i = 0; i < k; i++){
sum += arr[i];
}
int ret = 0;
for(int i = 0, j = k; j < n; i ++, j++){
if(sum / div >= threshold ){
ret++;
}
sum -= arr[i];
sum += arr[j];
}
if(sum / div >= threshold ){
ret++;
}
return ret;
}
};
main(){
vector<int> v = {2,2,2,2,5,5,5,8};
Solution ob;
cout << (ob.numOfSubarrays(v, 3, 4));
}입력
[2,2,2,2,5,5,5,8] 3 4
출력
3
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면서 윈도우 합을 갱신합니다.
- 공간 복잡도: O(1) — 추가적인 배열 없이 상수 개의 변수만 사용합니다.
참고로, 나눗셈 연산을 피하고 싶다면 sum >= threshold * k 조건으로 비교하면 되는데, 이 경우 오버플로우 가능성만 주의하면 됩니다. 또한 실수형(double) 대신 정수형 합을 유지하면 부동소수점 오차 없이 정확한 결과를 얻을 수 있습니다.