LeetCode 643 - Maximum Average Subarray I (Easy)

출처: https://leetcode.com/problems/maximum-average-subarray-i/

// LeetCode 643 - Maximum Average Subarray I (Easy)
// https://leetcode.com/problems/maximum-average-subarray-i/

// 문제 설명
// 정수 배열 nums(n개)와 정수 k가 주어진다.
// 길이가 정확히 k인 연속 부분배열 중 평균이 최대인 것을 찾아 그 평균값을 반환하라.
// 오차 10^-5 이하면 정답으로 인정된다.

// 제약 조건
// n == nums.length
// 1 <= k <= n <= 10^5
// -10^4 <= nums[i] <= 10^4

// Example 1
// Input : nums = [1,12,-5,-6,50,3], k = 4
// Output: 12.75000
//   최대 평균 (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
//
// Example 2
// Input : nums = [5], k = 1
// Output: 5.00000

// 접근 — 고정 크기 슬라이딩 윈도우
// 평균이 최대 ⇄ 길이가 k로 고정이므로 "합이 최대"인 윈도우를 찾으면 된다.
// 1) 먼저 앞 k개의 합을 구해 첫 윈도우 합 sum과 최댓값 best로 둔다.
// 2) i = k 부터 끝까지 한 칸씩 밀며 sum += nums[i] - nums[i-k]
//    (새로 들어온 원소를 더하고, 빠진 원소를 뺀다 — 매번 다시 더하지 않음)
// 3) 매 단계 best = max(best, sum)
// 마지막에 best / k 를 double로 반환.
// 시간 O(n), 공간 O(1)

#include <vector>
#include <algorithm>
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];   // 첫 윈도우 합

        int best = sum;
        for (int i = k; i < (int)nums.size(); ++i)
        {
            sum += nums[i] - nums[i - k];             // 한 칸 밀기: 더하고 빼기
            best = max(best, sum);
        }

        return (double)best / k;                       // 마지막에 한 번만 실수 나눗셈
    }
};

정리

• 길이가 k로 고정이면 분모(k)가 일정하므로 “평균 최대”는 곧 “합 최대”와 같다. 합이 최대인 윈도우만 찾아 마지막에 한 번만 k로 나누면 된다.
• 매번 윈도우의 k개를 다시 더하면 O(n·k)다. 윈도우를 한 칸 밀 때 새로 들어온 원소를 더하고 빠진 원소를 빼는(sum += nums[i] - nums[i-k]) 보정만 하면 갱신이 O(1)이 되어 전체가 O(n)으로 떨어진다. 이 “직전 결과 재활용”이 슬라이딩 윈도우의 핵심이다.
• best를 0이 아니라 첫 윈도우 합으로 초기화해야 한다. 0으로 두면 모든 원소가 음수인 입력에서 오답이 난다.
• 정수 합을 끝까지 유지하다 마지막에만 (double)best / k로 실수 나눗셈한다. 매 스텝 나누는 것보다 부동소수 오차가 적고 연산도 줄어든다.
• 시간 O(n), 공간 O(1). 검증: 예제 2개 모두 통과(MSVC /std:c++17 컴파일·실행).