효율성(슬라이딩 윈도우) 5. 최대 매출

문제

 

배열이 주어질때 k번 만큼 연속되는 숫자의 합이 가장 큰 값은 무엇인가?

예를 들어 12 15 11 20 25 10 20 19 13 15의 배열 값이 있을때
k가 3이라면, 11 + 20 + 25 = 56 값이 가장 큰 합이 된다.

 

 

풀이

 

 

코드

 

function solution(k, arr){
  let answer = sum = 0;
    for (let i = 0; i < k; i++) sum += arr[i]; //처음 윈도우 값 구하기 : (12 + 15 + 11)
    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));

 

 

아래는 시간 복잡도가 O(n^2)이라 비효율 적이다.

//이런문제는 슬라이딩 윈도우로 하는 습관을 들여 놓는게 좋다.
function solution(k, arr){
  let answer = [];
  let sum = tmp = 0;
  for(let pin = 0; pin < arr.length - 2; pin++) {
    //아래의 코드를 while문으로 만들어 본다.
    // sum += arr[pin];
    // sum += arr[pin+1];
    // sum += arr[pin+2];
    tmp = pin;
    while (tmp < k) {
      sum += arr[tmp++];
    }
    
    answer.push(sum);
    sum = 0;
    k++;
  }
  // return answer; //[38, 46, 56, 55, 55, 49, 52, 47]
  return Math.max(...answer); //56
}

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

 

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의