최대 매출(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

 

구현 알고리즘

Sliding Window 알고리즘 이용

const solution = (arr,k) => {
    let firstValue = arr.slice(0,k)
    .reduce((acc,cur)=>{
        return acc+cur;
    },0);
    let answer=[firstValue];
    let sum = firstValue;

    for(let i=k;i<arr.length;i++){
        sum+=arr[i]-arr[i-k];
        answer.push(sum);
    }
    console.log(answer);
    return Math.max(...answer);
}

const arr = [12,15,11,20,25,10,20,19,13,15];

console.log(solution(arr,3));

 

12,15,11,20,25,10,20,19,13,15

 

[12,15,11]을 더해준 값을 answer배열의 첫번째 값으로 잡아주었다.

for문을 이용해서

[12,15,11] -> [15,11,20] -> [11,20,25] 이러한 방식으로 진행해주었다.

맨 처음 3원소들의 합계는 38이고 그 다음 원소들의 합계는 46이다.

[12,15,11] -> [15,11,20]으로 넘어갈때마다 세 원소들의 합계를 구해주려면 반복문이 한개 더 필요하다. 굳이 그렇게 할 필요 없이

12+15+11+20-12를 해주면 15+11+20의 값이 나오게 된다. 이러한 방식으로 반복문으로 전달받은 arr의 모든 구간을 계산해준뒤

answer 배열에 push를 해준다. 최종적으로는 가장 큰값을 return 해주어야하기 때문에, Math객체의 메소드인 max를 이용하여서 answer 배열에서 가장 큰 값을 찾아 return 해준다.

 

출력결과