[백준] 11659번: 구간 합 구하기 4 (Node.js)

 

접근방식

처음에 풀기 시작했을 때는, 주어진 배열에 a번~b번까지 자르고 더하고 콘솔!.... 이라고 너무 안일하게 풀었었습니다.

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 num = input[0].split(" ")[1];
  const arr = input[1].split(" ").map(Number);
  input.splice(0, 2);
  const jogun = input.map((v) => v.split(" "));
  for (let i = 0; i < jogun.length; i++) {
    let start = jogun[i][0];
    let end = jogun[i][1];
    let sum = arr.slice(start - 1, end).reduce((a, b) => a + b, 0);
    console.log(sum);
  }
});

 

어디에 내놔도 부끄러운 내 코드..😥

 

결과값은 괜찮게 나왔으나, 

 

당연하게 뜨는 메모리 초과로 인해 다른 방식으로 풀기 시작했습니다!

 

예를 들어 [5, 4, 3, 2, 1] 배열에서  1부터 3까지의 인덱스합을 구하려면

4 + 3 + 2를 더해야하는건데, 이는 매번 배열을 순회하면서 더하게 됩니다.

이렇게 하면 시간복잡도가 O(N)이 되는데, 즉 배열 크기만큼 반복해야 합니다.

 

하지만 특정 구간의 합을 미리 구해놓으면,

예를 들어 Array[3] - Array[0] 과 같이 배열을 매번 순회하는 것이 아닌 정해진 구간에서의 계산을 하게 되므로

시간복잡도가 O(1)이 됩니다.

 

O(N) : 입력 크기에 비례해서 시간이 늘어나는 경우. 즉, 배열에서 부분합을 매번 직접 계산하는 경우, 배열의 크기만큼 연산을 해야 하므로 O(N)의 시간이 걸립니다.
O(1) : 입력 크기와 상관없이 일정한 시간이 걸리는 경우. 즉, 미리 계산된 배열을 사용해서 특정 구간의 합을 구하는 경우 O(1)에 해당합니다.

 

 

풀이 ⏰

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 () {
  // [N, M] 값 설정
  const [N, M] = input[0].split(" ").map(Number);
  // 순회할 배열 설정
  const arr = input[1].split(" ").map(Number);
  input.splice(0, 2);
  // jogun = [[1, 3], [2, 4], [5, 5]]
  const jogun = input.map((v) => v.split(" "));
  // sumArr = [0, 0, 0, 0, 0, 0]
  const sumArr = Array(N + 1).fill(0);
  for (let i = 1; i <= N; i++) {
    // sumArr = [0, 5, 9, 12, 14, 15]
    sumArr[i] = sumArr[i - 1] + arr[i - 1];
  }
  for (let i = 0; i < M; i++) {
    // jogun[0] = 1, 3
    // jogun[1] = 2, 4
    // jogun[2] = 5, 5
    const [start, end] = jogun[i];
    // ex) jogun[0]에서는 1부터 3까지의 숫자의 합이므로 12가 나옵니다.
    // 미리계산된 12에서 0을 빼면서 그대로 12를 출력
    const result = sumArr[end] - sumArr[start - 1];
    console.log(result);
  }
});

 

백준 11659번 링크

👉 https://www.acmicpc.net/problem/11659