[자바스크립트] 최대 매출 (Sliding Window)

문제

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속 된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 15 11 20 25 10 20 19 13 15

연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.

▣ 입력설명
첫 줄에 N(5<=N<=100,000)과 M(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

▣ 출력설명
첫 줄에 최대 매출액을 출력합니다.

▣ 입력예제 1
10 3
12 15 11 20 25 10 20 19 13 15

▣ 출력예제 1 56

function solution(k, arr) {
        let sum = 0;
        let answer = 0;
        for (let i = 0; i < k; i++) {
          sum += arr[i];
          answer = sum;
        }
        for (let i = k; i < arr.length; i++) {
          sum += arr[i] - arr[i - k];
          answer = Math.max(answer, sum);
        }
        return answer;
      }

      let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
      console.log(solution(3, a));

Key

슬라이딩 윈도우 기법 (Sliding Window)

 

예를들어, 12 15 11 20 25 가 있다고 가정하고 연속된 3개의 숫자의 합의 최댓값을 구한다고 가정할 때 아래 3가지의 경우의 수가 나온다.

[12, 15, 11], 20 25

12, [15, 11, 20], 25

12, 15, [11, 20, 25]

이 과정에서 최소한의 계산으로 다음 배열의 합을 구하는 방법은

1. 처음 배열의 합을 구한다. ( 12+15+11=38 )
2. 다음 배열 [15, 11, 20]은 [12, 15, 11] 배열에서 맨 앞의 값을 빼고 그 다음 값인 20이 들어온 모습이다. 따라서 합은 ( 38-12 ) 26이다.

이렇게 고정 사이즈의 윈도우가 이동하면서 윈도우 내의 있는 데이터를 이용해 문제를 푸는 알고리즘을 슬라이딩 윈도우 기법이라고 한다.