[백준] 2003. 수들의 합 2

문제 링크

[백준] 2003. 수들의 합 2

풀이 과정

이중 for문으로 문제를 풀어도 시간 내에 해결되지만, 투 포인터를 활용할 시 시간을 더 단축시킬 수 있습니다.

while (right <= N) {
    if (sum <= M) sum += arr[right++];
    else sum -= arr[left++];

    if (sum === M) cnt++;
}

left 포인터는 누적 값 sum 에서 요소를 제거하는 역할을, right 포인터는 누적 값 sum 에 요소를 추가하는 역할을 합니다.

• sum 이 m 이하일 시, sum 에 right 포인터가 가리키는 요소를 누적시킵니다.
• sum 보다 클 시, sum 에서 left 포인터가 가리키는 요소를 제거합니다.
• sum 이 M일 시, 경우의 수를 추가해줍니다.

코드

const fs = require("fs");
const stdin = (process.platform === "linux"
    ? fs.readFileSync("/dev/stdin")
    : `10 5
1 2 3 4 2 5 3 1 1 2`
)
    .toString()
    .trim()
    .split("\n");
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const [N, M] = input().split(" ").map(Number);
const arr = input().split(" ").map(Number);
let left = 0,
    right = 0,
    sum = 0,
    cnt = 0;

while (right <= N) {
    if (sum <= M) sum += arr[right++];
    else sum -= arr[left++];

    if (sum === M) cnt++;
}

console.log(cnt);