2022/01/28) 5. 최대 매출 [효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)]

1. 문제

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

2. 해결 방법

1. 두 개의 for문을 써서 이 문제를 해결한다면, 시간 복잡도가 10*3=30이 된다. 그러므로 '슬라이딩윈도우'를 써서 구한다. 슬라이딩윈도우란 움직이는 창문이라고 생각하면 된다.
   총 6개의 칸이 있는 창이고 하나의 창문이 3칸을 차지 한다면, 창문은 1~3칸 & 2~5칸 & 3~6칸 이런 식으로 움직인다는 걸 생각해봐라.
2. 첫 번째 창문의 무조건 먼저 구해놓고(for문 조건을 k까지로 둚), 밀고 나가야 한다(sum+arr[i]-arr[i-k].

3. 정답

<script>
            function solution(k, arr){ //sum+arr[i]-arr[i-k] 첫번째창문을 무조건 구해놓고 밀고 나가야함
                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));
        </script>

4. 내 코드와 비교 그리고 칭찬

꺄하핳 솔직히 정말 쉬운 문제였긴 한데, 아직 조건문을 완벽하게 구현해내는 실력이 부족해서 바로 정답이 나오진 않았었다. 처음에 while문 조건을 반대로 했고, sum을 초기화하지 않았기 때문! 그치만 해냈다! 원래 오늘은 피곤하니까 패스해야지하고 안하려 했는데, 잠이 안오는군.. 공부하라고 이러나 보다. 좋아. 파이팅하자. 헐 대박 드디어 내가 슬라이딩윈도우를 해봤구나. 알고리즘에 대해서 하나도 모를 때, 옆에서 모누가 이 문제 푸는 거 보고 엄청 대단하다고 느꼈었는데.. ㅠㅠㅠ 심장이 두근두근된다. 근데 생각보다 별 건 아니네 ㅋㄷ

<script>
            function solution(k, arr){ //최대 매출액의 합을 구한다.
                let answer = 0, max = Number.MIN_SAFE_INTEGER, sum = 0;;
                let n = arr.length - 2; 
                let p = 0;
                for(let i = 0; i < n; i ++){
                    while(p <= 2){
                        sum += arr[i + p++];
                    }
                    (max < sum) ? max = sum : sum = max;
                    p = sum = 0;
                }
                answer = max;
                return answer;
            }
            let a=[12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
            console.log(solution(3, a));
        </script>