1806 부분합 (자바스크립트)

문제

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

입력

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

출력

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

===

문제 분석

배열의 길이가 작았다면 이중 반복문을 통해 가장 짧은 길이를 출력하면 되겠지만, 이 문제의 경우 최대 길이가 10만이므로 

이중 반복문을 돌린다면 시간 초과가 나올 것이다. 그래서 빅오 N의 방식으로 순회하는 걸 생각해봤는데 

인덱스 0부터 합이 m이 나올때까지 인덱스를 늘려준다. 

0~x까지의 합이 m 일때, 1부터 x까지의 합이 m이 또 나올 수 있다. 그러면 길이는 더 줄어든 것으로 answer가 된다.

그렇다면 합이 m이상일때까지 앞의 인덱스를 계속 증가시켜본다.

이제 m 미만이 된다면 다시 끝 인덱스를 증가 시켜가면서 m이상 되는 것을 찾아본다.

그리고 다시 앞 인덱스를 증가시켜가는 앞의 행위들을 반복한다.

이 과정에서 합이 m이상이 되면 그때마다 뒤 인덱스 - 앞 인덱스 +1 이 길이가 되므로 이것을 answer와 비교하면서 최솟값을 넣어준다.

const main = (n, m, arr) => {
    const INF = 1_000_000_000;
    let answer = INF;
    let left = 0;
    let right = 0;
    let s = 0;
    while (right < n) {
        s += arr[right];

        while (s >= m) {
            s -= arr[left];
            answer = Math.min(answer, right - left + 1);
            left++;
        }
        right++;
    }

    console.log(answer);
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map((v) => +v);
const arr = input[1].split(' ').map((v) => +v);
if (arr.reduce((acc, cur) => acc + cur, 0) < m) {
    console.log(0);
    process.exit(0);
}

main(n, m, arr);