[백준 #1806] 부분합, 자바스크립트 풀이

문제 난이도	유형
🥇골드 4티어	투 포인터 알고리즘

 

문제

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초	128 MB	59814	15970	11186	25.388%

 

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

 

입력

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

 

출력

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

 

예제 입력

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

 

예제 출력

2

---

풀이

연속된 수들에서 조건을 만족하는 부분합의 최소 길이를 알아내야한다. 전형적인 투 포인터 알고리즘 문제이다. 아래와 같이 start, end 두 개의 포인터를 둔 이후 조건에 맞는지 찾아나가면서 조건에 맞는 경우 최소 구간을 갱신해나가면 된다.

출처: https://butter-shower.tistory.com/226

 

코드

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  const [N, S] = input[0].split(" ").map(Number);
  solution(input[1].split(" ").map(Number), N, S);

  process.exit();
});

function solution(arr, N, S) {
  const notFound = N - 0 + 1;
  let answer = [0, N];
  let start = 0;
  let end = 0;
  let partialSum = arr[start];
  while (start < N && end < N) {
    if (partialSum >= S) {
      if (end - start < answer[1] - answer[0]) {
        answer = [start, end];
      }
      partialSum -= arr[start];
      start++;
    } else {
      end += 1;
      partialSum += arr[end];
    }
  }

  const result = answer[1] - answer[0] + 1;
  if (notFound === result) console.log(0);
  else console.log(result);
}