2022/01/27) 4. 연속부분수열2 [효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)]

1. 문제

<연속부분수열2>
: N개의 수로 이루어진 수열이 있다. 이 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성한다.
만약 N=5, M=5이고 수열이 다음과 같다면 1 3 1 2 3 합이 5가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3},
{1, 3, 1}로 총 10가지이다.

2. 해결 방법

1. 일단 이 코드는 꼭 기억해라. sum-=arr[lt++]; 그리고 answer=rt-lt+1;
2. arr[rt]를 더한 값이 m보다 작다면, rt-lt+1을 해주어서 answer에 더해주고, m보다 크다면 그 값이 작아질 때까지 while문을 돌려서 sum -=arr[lt++]을 해준다.
   

3. 정답

        <script>
            function solution(m, arr){
                let answer=0, sum=0, lt=0;
                for(let rt=0; rt<arr.length; rt++){
                    sum+=arr[rt];
                    while(sum>m){
                        sum-=arr[lt++];
                    }
                    answer+=(rt-lt+1);
                }               
                return answer;
            }
            let a=[1, 3, 1, 2, 3];
            console.log(solution(5, a));
        </script>

4. 내 코드와 비교 그리고 반성

진짜 돌머리같은 내 머리가 너무 한탄스럽다. 어디가 틀렸는지 모르겠다. 복습할 것이므로 일단 시간상 패스한다.

        <script>
            function solution(m, arr){
                let answer = 0, p2 = 1;
                for(let p1 = 0; p1 < arr.length; p1++){
                    sum = arr[p1];
                    if(sum<=m)answer++;
                    while(sum <= m && p2<arr.length){
                        sum += arr[p2++];
                        if(sum<=m)answer++;
                    }
                }
                return answer;
            }
            let a=[1, 3, 1, 2, 3];
            console.log(solution(5, a));
        </script>