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

1. 문제

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

2. 해결방법

1. 이 문제가 찐투포인터라고 한다. 어떻게 하면 투포인터로 풀 수 있을까? sum과 lt와 rt를 선언하고, for문을 돌리며 arr[rt]를 sum에 누적할건데, 만약 sum값이 m보다 크거나 같다면 arr[lt]를 sum에서 빼준 후 증가(++)해주고, sum값이 m보다 작다면 rt값을 증가시킨다.
2. 그러므로 rt가 끝나면 아예 끝나는 것이다.(sum값이 작을 때 rt를 증가시켰으므로)
3. sum === m이 된다면 answer++; 해준다.
4. 정리 : 계속 arr[rt]값을 sum에 누적하는데 이 sum값이 m과 같아진다면 answer++;해주고, 이 sum값이 m값보다 크거나 같다면 arr[lt]값을 빼준 후 증가시켜주면 되는데 여기서도 마찬가지로 sum값이 m과 같다면 answer++; 해주어야 한다.

3. 정답

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

4. 내 코드와 비교

답이 3이 나와야 하는데, 1이 나온다. 어디가 틀렸는지 모르겠다.

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