[백준] Node.js / 3273 - 두 수의 합 (투 포인터, 누적 합)

1806번: 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

예제 입력 1 

10 15
5 1 3 5 10 7 4 9 2 8

 

예제 출력 1 

2

 

나의 풀이

이 문제는 내가 투 포인터 알고리즘을 정리한 글의 예제와 거의 똑같은 문제이다.

다음 글을 참고하면 좋을 것 같다.

투 포인터(Two Pointers) 알고리즘

 

 

 

 

코드

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = Number(input[0].trim().split(" ")[0]);
const S = Number(input[0].trim().split(" ")[1]);
const arr = input[1]
  .trim()
  .split(" ")
  .map((x) => Number(x));
let start = 0;
let end = 0;
let intervalSum = arr[0];
let answer = N;
let isAnswer = false;

while (end < N) {
  if (intervalSum >= S) {
    isAnswer = true;
    if (end - start + 1 < answer) {
      answer = end - start + 1;
    }
    intervalSum -= arr[start++];
  } else {
    intervalSum += arr[++end];
  }
}
if (!isAnswer) answer = 0;

console.log(answer);

 

---

위에 내가 링크를 걸어둔 투 포인터 개념 예제와 똑같음을 알았지만, 다시 풀어보니 몇가지를 놓쳤었다.

 

처음엔 부분합을 아래 코드처럼 구현했었다. 매번 부분합을 구하는 방식인데 이는 반복문을 한번 더 쓰게 되어서 시간 초과가 뜬다. 이는 위 코드와 같이'누적 합'을 이용하면 해결할 수 있다.  

if (start !== end) {
    for (let i = start; i <= end; i++) {
      intervalSum += arr[i];
    }
  } else {
    intervalSum = arr[start];
}