[투포인터] 연속 부분수열 - (2)

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

N개의 수로 이루어진 수열이 주어진다.

이 수열에서 연속 부분 수열의 합이 특정 숫자 M 이하가 되는 경우가 몇 번 있는지 그 횟수를 세고 출력한다.

 

만약 1 3 1 2 3 의 수열이 주어지고 M=5라면 합이 5 이하가 되는 연속 부분 수열은 다음과 같다.

{1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3}, {1, 3, 1}

 

 

👉 입력

첫 번째 줄에 N과 M이 주어진다.

두 번째 줄에 N개의 원소를 가진 수열이 주어진다.

이때 각 원소들은 1000을 넘지 않는 자연수이다.

 

 

👈 출력

연속 부분 수열의 합이 M 이하가 되는 경우의 수를 출력한다.

 

 

📝 풀이

 

function solution(m, arr) {
    let answer = 0;
    let start = 0;
    let sum = 0;

    for (let end = 0; end < arr.length; end++) {
        sum += arr[end];
        while (sum > m) sum -= arr[start++];
        answer += (end - start + 1);
    }
    return answer;
}

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

 

투 포인터 알고리즘을 사용하기 위해 변수 start를 선언하고 0으로 초기화한다.

나머지 포인터인 end는 for문을 돌며 배열의 각 요소를 순회한다.

 

연속 부분 수열의 합이 특정 숫자 M 이하가 되는 경우를 세는 문제이므로 일단 end가 가리키는 배열의 요소를 더해 sum 값을 구한다.

 

sum의 값이 m보다 크다면 start가 가리키던 요소의 값을 sum에서 뺀 뒤 start에 1을 더한다.

sum 값이 m보다 작다면 우리가 찾는 경우의 수이므로 answer에 해당 값을 더해 경우의 수를 센다.

 

경우의 수가 end - start + 1이 되는 이유는 다음과 같다.

 

 

end가 움직이며 새로운 수가 sum에 더해질 때, start가 움직이며 sum이 다시 M보다 작아질 때 새로 만들 수 있는 연속 부분 수열의 수를 구하는 것이다.

즉, end가 움직이면 새로운 수가 추가되어 만들 수 있는 연속 부분 수열을, start가 움직이면 기존 start가 가리키던 요소를 뺀 나머지의 수가 만들 수 있는 연속 부분 수열의 수를 구한다.

따라서 이를 수식으로 표현하면 end - start + 1이 된다.