[백준 1806 - Node.js] 부분합

🔗 문제 링크

https://www.acmicpc.net/problem/1806

1806번: 부분합

✏️ 풀이

const [[N, S], arr] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(v => v.split(' ').map(Number));

let sum = 0;
let minLength = Infinity;
let i = 0;
let j = 0;

while (j < N) {
  sum += arr[j];

  while (sum >= S) {
    sum -= arr[i];
    minLength = Math.min(minLength, j - i + 1);
    i++;
  }

  j++;
}

console.log(minLength === Infinity ? 0 : minLength);

투 포인터를 사용하여 해결하였다.

부분합의 시작점을 i, 끝을 j라고 할 때, 반복문을 통해 j를 증가시키면서 arr[j]를 sum에 누적한다. sum이 S 이상일 때 sum이 S 미만이 될 때까지 i를 증가시키면서 sum이 S 이상일 때의 길이(minLength)를 갱신한다. 반복문이 끝난 후에 minLength가 갱신된 적이 없다면 0을, 그 외에는 minLength를 반환하면 된다.