[백준 16139] 인간-컴퓨터 상호작용 - 누적합, javascript,node.js

문제:

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

16139번: 인간-컴퓨터 상호작용

알고리즘 :

1. 특정 알파벳 마다 누적합의 개수를 저장하기 위해 map을 이용한다.

- map을 사용하지 않고 일일이 누적합을 구할 시 50점을 받게 된다.

 

2. 누적합의 개수를 구할 때는 map.get을 이용한다.

 

전체코드

 

const filePath = require('path').join(__dirname, '/test.txt');
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');


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

const [ str ,count] = [input[0],input.length-2]

const map = new Map()
const answer = []


for(let i=0;i<count;i++){
  const [cur] = input[2+i].split(' ')
  const [s,e] = input[2+i].split(' ').slice(1).map(Number)
  if (!map.has(cur)) {
    let psum = new Array(str.length+1).fill(0)
    for(let j=0;j<str.length;j++){
      let sum = str[j]===cur?1:0 
      psum[j+1] = psum[j] + sum
    }
    map.set(cur,psum)
  }

  answer.push(map.get(cur)[e+1]-map.get(cur)[s])
}

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