백준16139 - 인간-컴퓨터 상호작용 (누적합) node.js

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

 

문제 해결 방식

해당 문제의 경우는, 특정 질문에서 a~b 구간의 특정 알파벳 등장 횟수를 출력하는 문제다.

이때, a~b 구간에서 등장한 모든 알파벳의 갯수를 매 쿼리마다 구하는 것은 시간 복잡도에서 불리하다.

 

따라서 문자열 길이에 맞는 테이블을 구현 후, 각 인덱스마다 특정 알파벳이 몇번 등장했는지 기록하는 자료 구조를 구현했다.

이를 활용할 경우, b 인덱스까지 등장한 알파벳의 갯수와 a 인덱스까지 등장한 알파벳의 갯수의 차가 곧 우리가 구해야 할 값이 된다.

 

전체 소스 코드

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

function solution(data) {
  const [str, n, ...query] = data;

  const table = {};
  table[-1] = Array.from({ length: 26 }, () => 0);

  for (let i = 0; i < str.length; i++) {
    table[i] = [...table[i - 1]];
    const char = str[i].charCodeAt() - 97;
    table[i][char]++;
  }

  const result = query.map((el) => {
    const [alp, s, e] = el.split(" ").map((x) => (!isNaN(x) ? +x : x));
    const char = alp.charCodeAt() - 97;
    return table[e][char] - table[s - 1][char];
  });

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

solution(input);