백준1806 - 부분합 (두 포인터) node.js

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

해당 문제는 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구하는 문제다.

 

문제 풀이 방식

부분 합을 구하기 위해서 두 포인터를 활용하여 문제를 해결하였다. 부분합의 길이는, 인덱스로 삼고 있는 right와 left의 차라는 것만 기억하면 풀이는 그리 어렵지 않다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const [[N, M], arr] = data.map((el) => el.split(" ").map(Number));

  let [left, right, sum] = [0, 0, 0];
  const result = [];
  while (right <= N) {
    if (sum >= M) {
      result.push(right - left);
      sum -= arr[left];
      left++;
    } else {
      sum += arr[right];
      right++;
    }
  }

  console.log(result.length ? Math.min(...result) : 0);
}

solution(input);