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

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

 

 

 

 

📋 문제

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

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

 

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

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

 

 

👉 입력

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

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

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

 

 

👈 출력

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

 

 

📝 풀이

 

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

    while (start < arr.length) {
        while (end < arr.length && sum < m) {
            sum += arr[end++];
        }
        if (sum === m) {
            answer++;
        }
        start++;
        end = start;
        sum = 0;
    }
    return answer;
}

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

 

투 포인터를 사용하기 위해 그 역할을 할 start와 end를 선언 후 0으로 초기화했다.

첫 번째 while문에서는 start를 움직이고 두 번째 while문에서는 end를 움직인다.

 

두 번째 while문에서 end가 정해진 배열의 범위 내로 움직이며 sum이 특정 숫자 m보다 크거나 같게 되면 while문을 빠져나와 이때 sum이 m과 같은지 비교한다.

만약 같으면 경우의 수를 저장할 answer에 1을 더해준다.

같지 않을 경우에는 이제 비교할 필요가 없으므로 start 지점을 1칸 옮기고 sum과 end의 값을 초기화한다.

이후 다시 반복문을 돌며 연속 부분 수열을 만들고 특정 구간의 합이 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) {
            if (sum === m) answer++;
            sum -= arr[start++];
        }
    }

    return answer;
}

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

 

투 포인터를 사용하는 방식이 비슷하면서 다르다.

둘을 같이 선언하는 것이 아닌 start만 선언하고 for문 안에서 end가 돌게 된다.

 

for문 안에서 end가 돌며 sum을 저장한다.

이때 sum이 m보다 같거나 커지게될 때, 만약 sum이 m과 같다면 answer에 1을 더한다.

같지 않다면 sum이 m보다 커지게 됐다는 뜻이기 때문에 sum에서 start가 가리키는 arr의 원소 값을 뺀 후 start를 옮긴다.