[LeetCode] #643. Maximum Average Array

문제 :

 

문제는 간단하다. 배열의 위치(인덱스)를 바꾸지 말고, 파라미터로 주어진 k개의 요소만큼의 subarray를 검사하여, 합 / k가 최댓값이 되는 최대 평균값을 구하여라.

 

이 문제는 Sliding window를 활용하는 문제였다. 감격적인 순간! 배열문제를 풀면서 슬라이딩 윈도우를 종종 접하곤 했었는데, 사실 모르는 주제라 그냥 넘어가거나, brute force를 이용해 풀어왔다. 하지만 이번 기회에 sliding window를 직접 구현해보며 뭔지 알고 넘어 가겠다!

 

코드:

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        max_sum = now_sum = sum(nums[:k])
        for idx in range(k, len(nums)):
            now_sum += nums[idx] - nums[idx - k]
            max_sum = max(max_sum, now_sum)
        
        return max_sum / k

 

 

코드를 살펴 보기 전, Sliding Window란 무엇일까?

 

슬라이딩 윈도우(Sliding Window) 기법은 배열이나 문자열과 같은 연속된 데이터 구조에서 특정 조건을 만족하는 연속된 부분 집합(서브 배열 또는 서브 문자열)을 효율적으로 탐색하는 방법이다. 이 기법은 고정된 크기의 윈도우(부분 집합)를 사용하여 배열의 시작부터 끝까지 이동하면서 필요한 계산을 수행한다. 슬라이딩 윈도우 기법은 시간 복잡도를 줄이고 효율적인 연산이 가능하게 한다.

슬라이딩 윈도우의 기본 원리

1. 고정 크기 슬라이딩 윈도우
고정된 크기의 윈도우를 사용하여 데이터를 처리한다. 윈도우는 한 번에 한 칸씩 오른쪽으로 이동한다.

 

슬라이딩 윈도우의 개념을 읽어보고 예제를 좀 살펴보니 그렇게 복잡한것 같지는 않다. 아래는 위 코드에 대한 설명이다!

설명:
1. 초기 윈도우의 합을 계산한다.
2. 윈도우를 한 칸씩 오른쪽으로 이동하면서 각 윈도우의 합을 계산한다. 이동할 때마다 윈도우의 첫 요소를 빼고, 새로운 요소를 더한다.
3. 최대 합을 갱신한다.

 

여기서 궁금했던점이 있다. "이동할 때마다 윈도우의 첫 요소를 빼고, 새로운 요소를 더한다." 굳이 왜 이렇게 할까?

 

슬라이딩 윈도우 기법에서 각 반복마다 첫 요소를 빼고 다음 요소를 더하는 이유는 효율성을 극대화하기 위해서이다. 이를 통해 시간 복잡도를 줄이고, 전체 리스트를 다시 계산하지 않고도 부분 합을 업데이트할 수 있다; 사실 나도 같은 생각을 했다. 왜냐하면 두번째 슬라이딩에서는 이전에 더했던 3개의 값 +  새로운 값을 더해야 했다. 그래서 처음에 생각했던것이 : DP로 풀어야 하나...? 계산을 이미 한 것을 또 하는것은 너무 큰 낭비이기 때문에 반복문이 돌때마다 새로 계산 해 주는건 말도 안된다고 생각했다.

슬라이딩 윈도우 기법의 원리
1. 초기 합계 계산: 첫 번째 윈도우의 합을 구한다. 예를 들어, 리스트 `[1, 12, -5, -6, 50, 3]`에서 윈도우 크기 `k=4`일 때, 첫 번째 윈도우의 합은 `1 + 12 + (-5) + (-6)`이다.
2. 윈도우 이동: 다음 윈도우로 이동할 때, 기존 윈도우의 첫 요소를 빼고, 새로운 윈도우의 마지막 요소를 더한다. 이렇게 하면 매번 새로운 윈도우의 합을 계산할 필요 없이 기존 윈도우의 합을 이용하여 효율적으로 계산할 수 있다. (저장할 테이블이 없는 DP같단 생각이 들었다.)

위의 예제를 살펴보면, 

- 첫 번째 윈도우
첫 번째 윈도우는 `nums[0:4]`로, 합계는 `1 + 12 + (-5) + (-6) = 2`이다.

- 두 번째 윈도우
다음 윈도우로 이동할 때, 첫 번째 요소 `1`을 빼고 다음 요소 `50`을 더한다:

새로운 윈도우 합계 = 기존 합계 - 첫 번째 요소 + 새로운 요소
                 = 2 - 1 + 50
                 = 51


- 세 번째 윈도우
다음 윈도우로 이동할 때, 첫 번째 요소 `12`를 빼고 다음 요소 `3`을 더한다:

새로운 윈도우 합계 = 기존 합계 - 첫 번째 요소 + 새로운 요소
                 = 51 - 12 + 3
                 = 42


결국 슬라이딩 윈도우 기법에서 첫 요소를 빼고 새로운 요소를 더하는 이유는, 매번 새로운 윈도우 합을 전체적으로 계산하지 않고도 부분 합을 효율적으로 업데이트하기 위함이다. 이를 통해 시간 복잡도를 O(n)으로 줄일 수 있어, 큰 리스트에서도 빠르게 동작할 수 있다.