CODE KATA #30

최대 매출 (Sliding Window)

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

현수야 나만 믿어

나의 풀이 1

    for (let i = 0; i < arr.length - k; i++) {
      let sum = 0;
      for (let j = 0; j < k; j++) {
        sum += arr[i+j];
      }
      if(sum > answer) answer = sum;
    }

처음 문제를 접했을 때엔 이 방식으로 풀이를 진행했다. sliding window 알고리즘에 대한 개념이 없었고 심지어 시간 복잡도가 O(n^2)이 아니라 O(n*(n-k))이기 때문에 효율적인 방식으로 풀어냈다고 착각했다.

나의 풀이 2

            function solution(k, arr){
                let answer,window = 0;
                for (let i = 0; i < k; i++) {
                    window += arr[i];
                }
                answer = window;
                for (let j = 0; j < arr.length-k; j++) {
                    window = window - arr[j] + arr[j+k];
                    answer = answer < window ? window : answer;
                }
                return answer;
            }

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

강사님의 문제 설명에 대한 풀이를 듣고는 다음과 같이 풀어냈다. 과정은 다음과 같다. 0부터 k까지 반복하는 for문을 통해 첫번째 window를 만들어내고, 이후 0부터 arr의 길이 - k만큼 반복하는 반복문을 통해 j번째의 원소를 window에서 빼주고, j+k번째 원소를 window에 더해줌으로서 window가 k개의 원소를 유지하도록 했다. 각각의 window가 갱신될 때마다 초기값이 첫번째 window인 answer과 크기 비교를 통해 더 큰 값이 answer이 되도록 하였다.

정답 풀이

            function solution(k, arr){
                let answer, 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));

정답 풀이의 경우도 거의 똑같은 방식으로 풀이를 작성했다. 다만 삼항연산자를 통해 answer을 정해주었던 나와 달리, Math.max(answer,sum)을 통해서 더 큰 값을 확인하였다.