백준17390 - 이건 꼭 풀어야 해 (누적합) node.js

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

 

문제에서는 N개의 질문, Q개의 테스트 케이스 갯수, 원소가 숫자로 이루어진 집합, 그리고 합을 구하기 원하는 시작점과 끝점이 주어진다.

 

문제 접근 방식

문제에서 주어진 내용처럼, 먼저 숫자들이 원소로 주어진 집합을 정렬한 후 각기 테스트케이스에 맞는 합을 구해주면 된다.

다만 이때 테스트케이스가 주어질 때마다 합을 구하기 위해 새로 연산하는 것보다,

각 인덱스까지의 누적값을 해쉬 테이블에 저장한 뒤 활용해주는 방식으로 문제를 해결하는 것이 보다 시간을 절약할 수 있다.

 

전체 소스 코드

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

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

  arr.sort((a, b) => a - b);

  const table = {};
  table[0] = 0;

  arr.reduce((acc, cur, idx) => {
    table[idx + 1] = acc + cur;
    return acc + cur;
  }, 0);

  const result = testCase.map(([a, b]) => {
    return table[b] - table[a - 1];
  });

  console.log(result.join("\n"));
}

solution(input);