[슬라이딩 윈도우]최대 매출

문제

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

12 15 11 20 25 10 20 19 13 15

연속된 3일간의 최대 매출액은 56만원(11+20+25) 입니다.

 

문제풀이

K일 동안의 최대 매출액을 구하는 것이기 때문에 투포인터 lt와 rt가 각각 참조하고 있는 인덱스 간에 차이의 값(0일~k일까지)이 K가 될 경우 현재 최대 매출액을 비교해 주었다.

 

K값이 되었을 때 포인터 rt를 더 이동시켜도 K일을 넘어서 최대 매출액을 구하는 것은 문제의 요구 사항과 부합되지 않기 때문에 K값보다 작아지도록 포인터 lt를 이동시켜 준다.

 

이후 포인터 rt가 다시 다음 인덱스 요소를 참조하게 될 경우 인덱스 간에 차이의 값이 K가 되기 때문에 현재 최대 매출액을 비교해 줄 수 있다.

 

코드

function solution(arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let lt = 0;
  let sum = 0;

  for(let rt = 0; rt < arr.length; rt++) {
    sum += arr[rt];
    if(rt - lt + 1 === 3) {
      answer = Math.max(answer, sum);
      sum -= arr[lt++];
    }
  }
  
  return answer;
}

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

 

문제풀이2_슬라이딩 윈도우

슬라이딩 윈도우(Sliding Window) 알고리즘은 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용하다.

 

다음 그림과 같이 이루어진 배열 [12, 15, 11, 20, 25, 10, 30]에서 길이(K)가 3인 서브배열의 합계가 가장 큰 서브배열을통해 최대 매출액을 구할 수 있다.

 

서브배열은 K만큼 길이가 고정되어 있고 다음 인덱스로 하나씩 이동하게 되면 이전에 참조했던 인덱스 요소 중 가장 처음에적재되어 있는 인덱스 요소는 감산해주고 이후에 새롭게 참조되는 인덱스 요소는 가산해주면 된다.

 

코드

function solution(k, arr) {
  let answer = 0;
  let sum = 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 arr = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, arr));