n개의 정수로 이루어진 배열이 주어졌을 때, 길이가 k 이상인 연속된 부분 배열 중에서 평균값이 가장 큰 경우를 찾아야 합니다. 즉, 조건을 만족하는 부분 배열의 최대 평균값을 구하는 것이 목표입니다.
예를 들어 입력이 [1,12,-5,-6,50,3]이고 k = 4라고 가정해 보겠습니다. 길이가 5일 때 최대 평균은 10.8, 길이가 6일 때는 9.16667입니다. 따라서 정답은 12.75가 됩니다.
문제 해결 접근 방법
이 문제는 이분 탐색(Binary Search) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "평균값 x 이상을 만족하는 길이 k 이상의 부분 배열이 존재하는가?"라는 판별 함수를 만들고, 가능한 평균값 범위를 좁혀 가며 답을 찾는 것입니다.
판별 함수 ok(x)의 동작 원리는 다음과 같습니다.
- 배열의 각 요소에서 x를 뺀 값을 새로운 배열 arr에 저장합니다. 이렇게 하면 어떤 구간의 arr 합이 0 이상이라는 것은 해당 구간의 실제 평균이 x 이상이라는 의미가 됩니다.
- 먼저 처음 k개 요소의 합을 계산하여 0 이상인지 확인합니다.
- 이후 슬라이딩 윈도우 방식으로 구간을 확장하면서, 음수가 되는 앞부분(접두사)은 제거해 나갑니다. 이는 카데인 알고리즘(Kadane's Algorithm)과 유사한 아이디어로, 불필요한 음수 구간을 버리면 더 긴 구간에서도 합이 0 이상이 될 수 있는지 효율적으로 판단할 수 있습니다.
메인 함수에서는 low와 high 사이를 반복적으로 이분 탐색하며, 오차 범위가 10^-5보다 작아질 때까지 mid 값을 검사합니다. 조건을 만족하면 low를 올리고, 그렇지 않으면 high를 내려 탐색 범위를 좁힙니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(double x, vector <int>& nums, int k){
int n = nums.size();
double arr[n];
for (int i = 0; i < n; i++) {
arr[i] = nums[i] - x;
}
double sum = 0;
double last = 0;
for (int i = 0; i < k; i++) {
sum += arr[i];
}
if (sum >= 0)
return true;
for (int i = 0, j = k; j < n; i++, j++) {
last += arr[i];
sum += arr[j];
if (last < 0) {
sum -= last;
last = 0;
}
if (sum >= 0)
return true;
}
return false;
}
double findMaxAverage(vector<int>& nums, int k) {
double ret = 0;
double low = INT_MIN;
double high = INT_MAX;
while (high - low > 1e-5) {
double mid = low + (high - low) / 2;
if (ok(mid, nums, k)) {
low = mid;
ret = mid;
} else {
high = mid;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,12,-5,-6,50,3};
cout << (ob.findMaxAverage(v, 4));
}입력
{1,12,-5,-6,50,3},4출력
12.75000
시간 복잡도 분석
ok() 함수는 O(n) 시간에 동작하고, 이분 탐색은 오차 범위 10^-5까지 반복되므로 전체 시간 복잡도는 O(n × log((max-min)/ε))입니다. 여기서 ε은 허용 오차를 의미합니다. 이 방식은 모든 가능한 부분 배열을 직접 확인하는 브루트 포스 방식(O(n²))보다 훨씬 효율적입니다.