5-3) 연속 부분수열 1

김예지·2021년 9월 2일

[알고리즘] javascript 인프런 강의

목록 보기

38/91

문제

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
12131112
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.
[입력설명]
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다. 수열의 원소값은 1,000을 넘지 않는 자연수이다.
[출력설명]
첫째 줄에 경우의 수를 출력한다.

입력예제 1

8 6
1 2 1 3 1 1 1 2

출력예제 1

문제 풀이

코드

투포인터 알고리즘을 활용한 문제이다. lt(left pointer), rt(right pointer)의 초깃값을 0으로 잡는다. lt는 가만히 있고, rt가 계속 바뀌면서 값을 누적한다. 만약, 누적값이 m보다 커진다면, lt의 값을 하나씩 빼주고 lt포인터를 +1해준다.
시간 복잡도는 O(n)이다.
sum-=arr[lt++]는, sum=sum-arr[lt]를 실행한 후에, lt++를 실행한다.

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <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++;
                    //sum>=m일때는, sum===m이 될 때까지 lt의 값 빼줘야함 
                    while(sum>=m){
                        sum-=arr[lt++]; 
                        if(sum===m) answer++;//빼고나서도 바로 sum===m인지 확인
                    }
                }
                return answer;
            }
            
            let a=[1, 2, 1, 3, 1, 1, 1, 2];
            console.log(solution(6, a));
        </script>
    </body>
</html>

김예지

내가 짱이다 😎 매일 조금씩 성장하기🌱

이전 포스트

5-2) 공통원소 구하기

다음 포스트

5-4) 연속 부분수열2

1개의 댓글

김예지

2021년 9월 12일

while(sum>m){
                        sum-=arr[lt++];
                        if(sum===m) {
                            answer++;
                            sum-=arr[lt++];
                        }
}

코드를 간소화 하여 작성하면

while(sum>=m){
                        sum-=arr[lt++];
                        if(sum===m) answer++;
}

답글 달기