[알고리즘] 부분 수열의 합 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가지입니다.

풀이

function solution(m, arr){
    let answer=0;
    let sum =0;
    let lt=0;
    for(let rt=0;rt<arr.length;rt++){
        sum+=arr[rt]; //sum에 현재 rt 값을 누적
        while(sum>m) {
            sum-=arr[lt++];
        } //sum>m이 참일 때만 실행. sum에서 현재 lt 값을 빼주고 lt를 증감시킨다. sum>m이 거짓이 될 때까지.
        answer+=(rt-lt+1); //이외의 경우는 answer에 현재 rt 값을 포함해 만들어지는 모든 참의 경우의 수를 누적. 
    }
    return answer;
}

let a=[1, 3, 1, 2, 3];
console.log(solution(5, a));

• 나의 오답보다 훨씬 직관적이고 깔끔하다. while문을 잘 사용해야 할 것 같다.

나의 오답...

 function solution(m, arr){
    let answer=0;
    let sum =0;
    let lt=0;
    for(let rt=0;rt<arr.length;rt++){
        sum+=arr[rt]; //sum에 현재 rt 값을 누적
        if(sum<=m) answer+=(rt-lt+1); 
        //if문으로 조건에 맞는지 검증 후, 맞다면 현재 값을 포함한 모든 참의 경우를 answer에 누적.
        if(sum>m) {
            sum-=arr[lt++];
            if(sum<=m)answer+=(rt-lt+1);
        }; //다음 if문에서 조건에 부합하지 않는 경우 sum에서 lt값을 뺀 후 증감. 
        //다시한번 sum이 조건에 부합하는지 확인 후 참이되면 answer에 모든 경우 누적.
    }
    return answer;
}

let a=[1, 3, 1, 2, 3];
console.log(solution(5, a));

• 조건에 부합하지 않는 경우의 누적과정에서 누락된 부분이 있는듯...
• 부끄럽지만 나중에 보라고 올린다.