[C++] Maximum Average Subarray I

문제 - LeetCode 643. Maximum Average Subarray I

https://leetcode.com/problems/maximum-average-subarray-i/description/?envType=study-plan-v2&envId=leetcode-75

 

이번 문제는 정수 배열 nums와 정수 k가 주어졌을 때,
길이가 정확히 k인 연속 부분 배열 중 평균값이 가장 큰 값을 구하는 문제입니다.

평균을 구하려면 결국 부분 배열의 합이 커야 평균도 커지기 때문에,
이 문제는 사실상 “길이가 k인 subarray 중 합이 최대인 값을 찾는 문제”로 바꿔서 생각할 수 있습니다.

---

처음 접근: 이중 for문

for (int i = 0; i <= nums.size() - k; i++) {
    int sum = 0;
    for (int j = i; j < i + k; j++) {
        sum += nums[j];
    }
}

실제로 동작은 하지만…

문제점

• 매번 k개의 합을 다시 계산한다.
• 시간 복잡도: O(n × k)
• n = 100,000 / k도 큰 경우가 있으므로 시간 초과 가능성 높음

이 방식은 효율적이지 않습니다.

---

해결 방법

각 윈도우(부분 배열)는 한 칸씩 오른쪽으로 이동한다는 점에 주목했습니다.

예를 들어 k = 4일 때:

윈도우 1: nums[0], nums[1], nums[2], nums[3]
윈도우 2: nums[1], nums[2], nums[3], nums[4]

두 윈도우는 대부분 값이 겹칩니다.

• 빠지는 값: nums[i - k]
• 새로 들어오는 값: nums[i]

따라서 새로운 합은 이렇게 구할 수 있습니다:

새 합 = 이전 합
       - 빠지는 값
       + 들어오는 값

즉, 이전 합을 활용하면 O(1) 시간에 다음 합을 구할 수 있습니다!

---

슬라이딩 윈도우(Sliding Window) 적용

이 원리를 바탕으로 “슬라이딩 윈도우” 기법을 적용했습니다.

✔ 슬라이딩 윈도우 정의

“윈도우”라는 고정된 크기의 구간을 만들어 놓고,
이를 오른쪽으로 ‘미끄러지듯’ 이동시키며 필요한 값만 갱신하는 방식.

✔ 장점

• 매번 처음부터 합을 구하지 않아도 된다.
• 시간 복잡도: O(n)
  → 문제 조건에서 가능한 최고 효율

---

최적 코드

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        int sum = 0;

        // 첫 k개의 합 계산
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        int max_sum = sum;

        // 슬라이딩 윈도우 이동
        for (int i = k; i < n; i++) {
            sum += nums[i] - nums[i - k];
            if (sum > max_sum) max_sum = sum;
        }

        return (double)max_sum / k;
    }
};

 

* 참고로, max 함수를 사용하면 기존보다 느려졌다

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        int sum = 0;

        // 첫 k개의 합
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        int max_sum = sum;

        // 윈도우를 오른쪽으로 이동하면서 업데이트
        for (int i = k; i < n; i++) {
            sum += nums[i] - nums[i - k]; // 슬라이딩 윈도우
            max_sum = max(max_sum, sum);
        }

        return (double)max_sum / k;
    }
};