[JavaScript/section 5] 05 - 최대 매출

📌 05 - 최대 매출(슬라이딩 윈도우)

현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하는 문제이다.

나의 풀이 방법

• 이중 for 문을 돌며 처음부터 차례대로 K일 동안의 매출액을 구한다.
• answer 변수에 저장된 값과 sum을 비교하여 더 큰 값을 answer 변수에 넣어준다.

👍 강사님 풀이 방법(슬라이딩 윈도우)

고정 사이즈의 윈도우가 슬라이딩(이동)하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘❗❗

시간복잡도가 O(N)이기 때문에 이중 for 문을 이용한 방법보다 효율적이다.

• 배열의 첫 번째 인덱스에 해당하는 값부터 K 번째 인덱스까지의 합을 sum에 저장한다.
• answer 변수에 sum에 저장된 값을 넣어준다.
• 위의 과정이 고정 사이즈의 윈도우를 만들었다고 하면 이제 앞으로 쭈~욱 밀면서 최대값을 찾으면 된다.
• 윈도우가 한 칸 이동하면 sum에 arr[i]를 더하고 arr[i - k]를 빼준다. sum은 현재 윈도우 내에 있는 데이터의 합이다.
• answer 변수에 저장된 값과 sum을 비교하여 더 큰 값을 answer 변수에 넣어준다.

 

📝 풀이

// 나의 풀이 방법
function solution(k, arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let sum = 0;

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

  return answer;
}

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

// 강사님 풀이 방법
function solution(k, arr) {
  let answer;
  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 a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));