C++로 길이가 X 이상 Y 이하인 부분 배열의 최대 평균 구하기

문제 설명

정수 배열 arr[]과 두 개의 정수 X, Y가 주어집니다. 길이가 최소 X 이상, 최대 Y 이하인 모든 부분 배열 가운데 평균값이 가장 큰 부분 배열을 찾아 그 평균을 구하는 것이 목표입니다.

예시

입력 배열이 {2, 10, 15, 7, 8, 4}이고 X = 2, Y = 3일 때, 길이 2짜리 부분 배열 {10, 15}를 선택하면 최대 평균 12.5를 얻을 수 있습니다.

(10 + 15) / 2 = 12.5

접근 방법

길이가 X부터 Y 사이인 모든 부분 배열을 하나씩 살펴보며 그중 가장 큰 평균값을 기록합니다.
매번 구간합을 새로 계산하는 대신 접두사 합(prefix sum) 배열을 미리 만들어 두면, 어떤 부분 배열의 합도 O(1) 시간에 구할 수 있어 효율적입니다.

접두사 합 배열 prefix를 prefix[i] = arr[0] + … + arr[i]로 정의하면, 시작 인덱스가 i이고 끝 인덱스가 j인 부분 배열의 합은 prefix[j] - prefix[i-1](i > 0인 경우)로 즉시 계산할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 길이가 x 이상 y 이하인 부분 배열 중 최대 평균을 반환합니다.
double getMaxAverage(int *arr, int n, int x, int y) {
    // 접두사 합 배열 생성
    vector<int> prefix(n);
    prefix[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + arr[i];
    }

    double maxAverage = INT_MIN;

    // 시작 인덱스 i 결정
    for (int i = 0; i < n; ++i) {
        // 끝 인덱스 j는 i + x - 1부터 i + y - 1까지 가능
        for (int j = i + x - 1; j < i + y && j < n; ++j) {
            double sum = prefix[j];
            if (i > 0) {
                sum -= prefix[i - 1];
            }
            double current = sum / double(j - i + 1);
            maxAverage = max(maxAverage, current);
        }
    }
    return maxAverage;
}

int main() {
    int arr[] = {2, 10, 15, 7, 8, 4};
    int x = 2;
    int y = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum average = " << getMaxAverage(arr, n, x, y) << endl;
    return 0;
}

실행 결과

Maximum average = 12.5

동작 원리

배열 전체의 접두사 합을 O(n) 시간에 미리 계산해 둡니다.
각 시작 인덱스 i에 대해, 길이 조건(X ≤ 길이 ≤ Y)을 만족하도록 끝 인덱스 j를 i + x − 1부터 i + y − 1까지(배열 범위를 벗어나지 않는 선에서) 이동시키며 평균을 계산합니다.
계산된 평균이 지금까지의 최댓값보다 크면 갱신하고, 모든 탐색이 끝난 뒤 최종 최댓값을 반환합니다.

복잡도 분석

시간 복잡도: O(n × (Y − X + 1)) — 각 시작 위치마다 최대 (Y − X + 1)개의 끝 위치를 검사합니다.
공간 복잡도: O(n) — 접두사 합 배열을 저장하기 위한 추가 공간이 필요합니다.

참고: 배열에 음수가 포함될 가능성이 있다면 최댓값 변수를 0이 아닌 INT_MIN으로 초기화해야 올바른 결과를 보장할 수 있습니다. 위 구현은 이러한 경우까지 고려해 작성되었습니다.