[JS][백준]16139_인간-컴퓨터 상호작용

문제 번호

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

 

 

 

알고리즘 분류

• 누적 합

 

문제 풀이

 일반적인 누적합 문제이다. 각 알파벳별로 누적합을 구해서 문제를 해결하면된다. 

2차원 배열을 만들어서 각 알파벳별로 누적합을 구한다음 문제에서 주어지는 구간에 사용된 알파벳의 수를 구하였다.

 

전체코드

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

function makeSum(s, sum) { // 부분합을 구한다.
  for (let i = 1; i <= s.length; i++) {
    let alpha = s[i - 1].charCodeAt() - 96;
    sum[alpha][i]++;
    for (let j = 1; j <= 26; j++) { // 무슨 알파벳인지. 1 =  a, 26 = z.
      sum[j][i] += sum[j][i - 1];
    }
  }
}
function main() {
  let answer = '';

  let sum = new Array(27).fill(null).map(_ => new Array(200001).fill(0)); // sum[i][j] : i 알파벳 j 번째까지 몇번 나왔는지.
  let s = input[0].trim();
  let q = +input[1];
  makeSum(s, sum);
  
  for (let i = 2; i <= q+1; i++) {
    let [a, l, r] = input[i].split(' ');
    l = +l + 1;
    r = +r + 1;    
    a = a.charCodeAt() - 96;
    //console.log(`${l} ${r} : ${sum[a][r] - sum[a][l - 1]}`);
    answer += sum[a][r] - sum[a][l - 1] + '\n';
  }

  console.log(answer.trim())
}
main();

특이사항