C++ 최대 평균 부분 배열 구하기 – 슬라이딩 윈도우 알고리즘 풀이

문제 개요

n개의 원소로 이루어진 배열이 주어졌을 때, 길이가 k인 연속된 부분 배열 중에서 평균값이 가장 큰 경우를 찾아 그 최대 평균값을 반환하는 것이 이번 문제의 목표입니다.

예를 들어 입력 배열이 [1, 13, -5, -8, 48, 3]이고 k = 4라고 가정해 보겠습니다. 이때 (13 + (-5) + (-8) + 48) / 4 = 12.0이므로 결과는 12.0이 됩니다.

접근 방법: 슬라이딩 윈도우

가능한 모든 부분 배열을 일일이 계산하는 브루트 포스 방식은 비효율적입니다. 대신 슬라이딩 윈도우(Sliding Window) 기법을 사용하면 배열을 한 번만 순회해서 답을 구할 수 있습니다.

핵심 아이디어는 간단합니다. 길이가 k인 현재 윈도우의 합에서 맨 앞 원소 하나를 빼고 뒤에 새로운 원소 하나를 더하면, 다음 윈도우의 합을 상수 시간 O(1) 안에 얻을 수 있다는 점입니다.

알고리즘 단계

sum := 0으로 초기화합니다.
i := 0부터 i < k까지 반복하며 sum := sum + nums[i]로 처음 k개 원소의 합을 구합니다.
maxi := sum으로 설정하여 초기 최댓값을 저장합니다.
i := k부터 i < nums.size()까지 반복하며 다음을 수행합니다.
- sum := sum + nums[i] - nums[i - k]로 윈도우를 한 칸 오른쪽으로 이동시킵니다.
- sum > maxi라면 maxi := sum으로 갱신합니다.
최종적으로 maxi / k를 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   double findMaxAverage(vector<int>& nums, int k) {
      int sum = 0;
      for (int i = 0; i < k; i++) {
         sum += nums[i];
      }
      double maxi = sum;
      for (int i = k; i < nums.size(); i++) {
         sum += nums[i] - nums[i - k];
         if (sum > maxi) {
            maxi = sum;
         }
      }
      return maxi / k;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,13,-5,-8,48,3};
   cout << (ob.findMaxAverage(v, 4));
}

입력

{1,13,-5,-8,48,3}, 4

출력

시간 및 공간 복잡도

배열 전체를 딱 한 번 순회하므로 시간 복잡도는 O(n), 별도의 자료구조 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 매번 k개의 합을 다시 계산하는 브루트 포스 방식의 O(n × k)와 비교하면 훨씬 효율적인 접근이라 할 수 있습니다.