5-5 최대 매출

문제

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속
된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 15 11 20 25 10 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.
여러분이 현수를 도와주세요.

풀이

function solution(k, arr) {
  let answer,
    sum = 0;
  let rt = 0,
    lt = 0;
  let max = Number.MIN_SAFE_INTEGER;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[rt++];
    while (rt - lt > k) sum -= arr[lt++];
    if (max < sum) max = sum;
  }

  answer = max;
  return answer;
}

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

투포인터를 이용해서 sum에 arr[rt]를 더해주었고 rt -lt 값이 k값보다  초과라면 sum에 arr[lt]를 계속 뺴주었습니다.

다른 풀이

function solution(k, arr) {
  let answer,
    sum = 0;
  for (let i = 0; i < k; i++) {
    sum += arr[i];
    //console.log(i, sum);
  }
  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(2, a));

윈도우 슬라이딩 기법을 이용해서 맨처음 k값만큼의 합을 더해 answer 에 저장해줍니다.

 

그리고 k부터 시작하는 for문을 만들어서 sum += arr[i] - arr[i-k]를 해주었습니다.

풀어서 설명드리자면 12,15,11,20,25 가 있고 k값이 3이라면

 

answer 에는 12+15+11 = 38 으로 저장을 해 둔뒤

 

k값만큼의 범위를 움직이는 것입니다.

 

answer 에 11 다음인  20 값을 더해주고 범위가 늘어났으니 맨 앞의 12를 뺴주는 방법입니다.