[BOJ] 구간 합 구하기 4 with JavaScript

JavaScript를 이용한 백준 11659 구간 합 구하기 4 문제를 풀이한 글입니다.

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한
1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N

풀이

처음 해당 문제를 읽었을 때 떠오르는 가장 직관적인 방법은
입력된 수를 배열에 저장하고 각각의 케이스마다 주어진 범위 만큼 배열의 돌고 그 합을
출력하는 방법이다. 다만 해당 방법으로 진행하게 될 경우 이중 루프가 발생해 N * M번 진행하게 되므로 주어진 시간내로 통과할 수 없게 된다. 이를 해결하기 위해서는 단일 루프내로 해결할 수 있는 방법을 사용해야 한다.
i번째 부터 j번째의 합은 처음부터 i-1째까지의 합과 처음부터 j번째까지의 합의 차와 동일하다
따라서 입력받은 수의 합을 저장하는 배열을 미리 만들고 범위가 주어지면 sum[j] - sum[i - 1]의 방식으로 도출할 수 있다.

+a

처음 시도에서 dp를 활용한 풀이를 진행 했음에도 시간 초과가 발생했다. M번 루프를 도는 동안 매번 console.log() 출력을 시도했는데 console.log()를 많이 반복하는 것은 많은 시간소요를 요구하므로 한번의 출력만 진행할 수 있도록 정답 값을 저장하는 배열을 추가적으로 생성했다.

알고리즘

• M번의 루프를 돌며 sumList[j] - sumList[i - 1]의 값을 answer 배열에 저장한다.

구현

/**
 * https://www.acmicpc.net/problem/11659
 * 
 * hint: 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 이므로 단순 이중 루프를 진행하게 될 경우 
 * n^2 시간 복잡도를 가지게 된다.
 * 따라서 루프를 M번만 돌아 해결할 수 있는 방식으로 문제으로 해결해야 한다.
 * DP 방식으로 구간합의 배열을 사전에 구하는 방식을 사용
 *
 * +a 처음 시도했을 시 M번 도는 루프속에서 console.log()를 진행하여 시간초과가 발생
 * console.log()를 M번 반복하는 것을 많은 시간을 소요하므로 answer 배열에 값을 넣어
 * 루프를 빠져나온 후 answer를 출력하는 방식으로 진행
 */

const fs = require('fs');
const input = fs.readFileSync('./input.txt').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const numList = input[1].split(' ').map(Number);
const ranges = input.slice(2);

const sumList = [0, numList[0]];
const answer = [];

for (let i = 1; i < N; i++) {
    sumList.push(numList[i] + sumList[i]);
}

for (let i = 0; i < M; i++) {
    const range = ranges[i].split(' ').map(Number);
    answer.push(sumList[range[1]] - sumList[range[0] - 1]);
}

console.log(answer.join('\n'));