[Leetcode/Sliding Window] 643. Maximum Average Subarray I

슬라이딩 윈도우(Sliding Window)
: 윈도우(특정 범위)가 있을 때, 윈도우 내부 요소의 값을 이용하여 문제를 풀이하는 알고리즘.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # 초기 윈도우 설정 (첫 k개의 합)
        current_sum = sum(nums[:k])
        max_sum = current_sum

        # 슬라이딩 윈도우 이동
        for i in range(k, len(nums)):
            current_sum += nums[i] - nums[i - k]  # 윈도우 이동 (새로운 값 추가, 오래된 값 제거)
            max_sum = max(max_sum, current_sum)   # 최댓값 갱신
        
        # 최댓값을 k로 나눠 평균 반환
        return max_sum / k

풀이 설명

1. 처음 k개의 합을 current_sum으로 설정 (O(k) 연산).
2. k부터 끝까지 반복하며:
   • 슬라이딩 윈도우 이동:
     • 가장 오래된 요소 nums[i - k]를 제거.
     • 새로운 요소 nums[i]를 추가.
   • max_sum을 갱신.
3. 최댓값을 k로 나눠 평균을 반환.

시간 복잡도

• O(N): 리스트를 한 번 순회(O(N))하면서 덧셈/뺄셈 연산(O(1))을 수행 → O(N).
• O(1) 추가 공간 사용: max_sum과 current_sum만 저장하므로 추가 메모리 사용이 거의 없음.

슬라이딩 윈도우 방식의 장점

✅ O(N)으로 해결 가능 (완전 탐색을 하면 O(N*k)로 비효율적임)
✅ 추가 공간 사용이 적음 (O(1))
✅ 덧셈과 뺄셈만 사용하므로 연산이 빠름