[javascript알고리즘] 최대 매출 - 슬라이딩윈도우 기법

✅ 슬라이딩 윈도우

• 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용
• 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용
• 투 포인터와 비슷하지만 고정 사이즈 윈도우를 사용!

✅ 문제

• 주어진 배열 arr에서 연속된 k개의 원소 합의 최대값을 구하라
• k : 슬라이딩 윈도우의 크기
• arr : 주어진 배열

👩‍💻 나의 풀이

// 이중 for문이기 때문에 시간복잡도 상에서 좋지 않음
function solution(k, arr) {
  let answer = 0;
  let sum = 0;
  let check = 0;
  for (let i = 0; i < arr.length - 2; i++) {
    for (let j = 0; j < k; j++) {
      sum += arr[i + j];
      check += 1;
    }

    answer = Math.max(answer, sum);
    sum = 0;
    check = 0;
  }

  return answer;
}

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

• 이렇게 풀면 시간복잡도 상으로 좋지 않다.

📃 슬라이딩 윈도우 활용 풀이

// 슬라이딩 윈도우 : 창문(계산할 범위)을 정해놓고 옆으로 밀듯이 구현 => for문을 한 번만 돌면 됨
function solution(k, arr) {
  let answer = 0;
  let sum = 0;

  // 첫 번째 sum
  for (let i = 0; i < k; i++) sum += arr[i];
  answer = sum;

  // arr[i] : sum에 새로 더할 값, arr[i-k] : sum에서 제외할 값
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    answer = Math.max(answer, sum);
  }
  return answer;
}
console.log(solution(3, [12, 15, 11, 20, 25, 10, 20, 19, 13, 15]));