[JavaScript] 백준 1806번 - 부분합

[문제]

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

1806번: 부분합

[풀이]

수열의 부분합을 구하는 문제로 투포인터 알고리즘을 활용하여 풀이하였습니다.

 

예시 1과 같이 길이가 N(10)인 수열 [ 5, 1, 3, 5, 10, 7, 4, 9, 2,  8 ]이 있을 때,

 

아래와 같이 start = 0 , end = 0, sum = 5 로 투포인터 탐색을 시작합니다.

 

5  <- start

1  <- end

3

5

10

7

4

9

2

8

 

만약 sum이 S(15)보다 작거나 같다면 end++을 해주어 sum에 수열[end]값을 더해 sum 크기를 키워줍니다.

만약 sum이 S(15)보다 크다면, 수열[start]값을 sum에서 빼주어 sum을 작게 만들고 start++를 합니다.

 

따라서 5 <= 15 이므로 end + 1인 수열[1]의 1을 바라보게 되고 sum은 6이 됩니다.

 

이런식으로 start와 end값이 N 보다 작을 때까지(수열의 마지막까지) 갱신하며 만약 sum이 S보다 큰 경우 end - start + 1을 통해 몇개의 숫자가 연속되어 있는지 구해 min을 갱신하여 줍니다.

 

탐색 과정은 아래와 같습니다.

 

start: 0 end: 0 sum: 5
start: 0 end: 1 sum: 6
start: 0 end: 2 sum: 9
start: 0 end: 3 sum: 14
start: 0 end: 4 sum: 24 => 15보다 크거나 같기 때문에 4 - 0 + 1 = 5 => min = 5로 갱신
start: 1 end: 4 sum: 19 => min = 4로 갱신
start: 2 end: 4 sum: 18 => min = 3로 갱신
start: 3 end: 4 sum: 15 => min = 2로 갱신
start: 3 end: 5 sum: 22 => 3은 기존 min 2보다 크기 때문에 갱신 X
start: 4 end: 5 sum: 17 => 2는 기존 min과 같아서 갱신 X
start: 5 end: 5 sum: 7
start: 5 end: 6 sum: 11
start: 5 end: 7 sum: 20 => 3은 기존 min보다 커서 갱신 X
start: 6 end: 7 sum: 13
start: 6 end: 8 sum: 15 => 3 갱신 X
start: 6 end: 9 sum: 23 => 4 갱신 X
start: 7 end: 9 sum: 19 => 3 갱신 X
start: 8 end: 9 sum: 10

 

따라서 연속된 최소 개수인 min 은 2가 됩니다.

[코드]

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

const [N, S] = input[0].split(" ").map(Number);
const numArr = input[1].split(" ").map(Number);

let start = 0;
let end = 0;
let min = Number.MAX_VALUE;

let sum = numArr[0];
while(start < N && end < N) {
    if(sum >= S) {
        if(min > end - start + 1) {
            min = end - start + 1;
        }
    }
    
    if(sum <= S) {
        end++;
        sum += numArr[end];
    } else {
        sum -= numArr[start];
        start++;
    }
}

min === Number.MAX_VALUE ? console.log(0) : console.log(min);