C++에서 길이가 k인 최대 평균 부분 배열 찾기

문제 소개

이 문제에서는 양수와 음수 값으로 이루어진 크기 n의 배열 arr[]와 정수 k가 주어집니다. 우리의 목표는 길이가 k인 부분 배열(subarray) 중 평균이 가장 큰 것을 찾는 것입니다.

모든 후보 부분 배열의 길이가 k로 동일하므로, 평균이 최대인 부분 배열을 찾는 문제는 곧 합이 최대인 부분 배열을 찾는 문제와 같습니다.

예제로 이해하기

입력: arr[] = {4, -1, 5, 6, -2, 4}, k = 3

출력: 10

설명: 길이가 3인 부분 배열 중 합이 가장 큰 것은 {-1, 5, 6}이며, 그 합은 10입니다.

해결 접근 방식

이 문제는 누적합(prefix sum) 배열을 활용하면 효율적으로 해결할 수 있습니다. 먼저 보조 배열 auxSumArray를 만들어 각 인덱스까지의 원소 누적 합을 저장합니다.

그다음, 특정 구간에 속한 부분 배열의 합은 두 누적합 값의 차이만으로 O(1) 시간에 계산할 수 있습니다.

구간 합 = auxSumArray[i] - auxSumArray[i-k]

배열 전체를 한 번 순회하면서 길이 k인 모든 부분 배열의 합을 비교하고, 최댓값을 갖는 시작 인덱스를 반환하면 됩니다.

C++ 구현 코드

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

int findMaxSubArrayAverage(int arr[], int n, int k) {
    if (k > n)
        return -1;

    int *auxSumArray = new int[n];
    auxSumArray[0] = arr[0];
    for (int i=1; i<n; i++)
        auxSumArray[i] = auxSumArray[i-1] + arr[i];

    int maxSum = auxSumArray[k-1], subEndIndex = k-1;

    for (int i=k; i<n; i++) {
        int sumVal = auxSumArray[i] - auxSumArray[i-k];
        if (sumVal > maxSum) {
            maxSum = sumVal;
            subEndIndex = i;
        }
    }

    return subEndIndex - k + 1;
}

int main() {
    int arr[] = {4, -1, 5, 6, -2, 4};
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"The maximum average subarray of length "<<k<<" begins at index "<<findMaxSubArrayAverage(arr, n, k);
    return 0;
}

실행 결과

The maximum average subarray of length 3 begins at index 1

위 실행 결과는 길이가 3인 최대 평균 부분 배열이 인덱스 1, 즉 {-1, 5, 6}에서 시작한다는 의미입니다.

복잡도 분석

• 시간 복잡도: O(n) — 누적합 배열 생성과 최대 합 탐색 단계에서 각각 배열을 한 번씩 순회합니다.
• 공간 복잡도: O(n) — 크기 n의 보조 누적합 배열이 필요합니다.

대안: 슬라이딩 윈도우 기법

보조 배열 없이 슬라이딩 윈도우(sliding window) 기법을 사용하면 공간 복잡도를 O(1)까지 줄일 수 있습니다. 처음 k개 원소의 합을 구한 뒤, 윈도우를 한 칸씩 오른쪽으로 이동하면서 새로 들어오는 원소는 더하고 빠져나가는 원소는 빼주면 됩니다. 이 방식 역시 시간 복잡도는 O(n)으로 동일합니다.