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

안녕하세요. 박기린 입니다.

백준 16139번 인간-컴퓨터 상호작용 문제를 풀어봅시다.

 

 

문제 링크

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

---

문제 해석

giraffe라는 글자와 [i 0 3]이라는 질문이 주어졌다고 가정합니다.

 

 

 

giraffe 문자열 중, 0번째부터 3번째까지의 글자 중에 i가 있는지 검사합니다.

i가 하나 있으므로, 1을 출력하면 정답입니다.

 

 

 

하지만, 매번 일일이 for문으로 모든 질문을 검사하게 된다면,

200,000자의 문자와 200,000개의 문제를 견뎌내기 힘들 것입니다. 그래서 누적합 방식을 사용합니다.

 

 

 

위처럼 f에 대한 질문이 여러 개 있을 경우,

미리 f의 갯수를 세어놓은 데이터를 만들어서, f 질문 때마다 뽑아쓰면 효율적일 것입니다.

 

 

 

 

DP라는 {key: value}형태의 딕셔너리를 만듭니다.

key는 어떤 알파벳을 검사했는지 담고,

value에는 array를 담습니다.

 

value로 들어가는 array는, giraffe와 동일한 길이를 가집니다. 

array[인덱스 번호]에는 giraffe라는 글자 중 인덱스 번호의 순서까지 총 몇 개의 똑같은 알파벳이 들어갔는지가 담깁니다.

 

DP[i][1] = 1입니다.
왜냐하면, giraffe라는 문자열에서 인덱스가 1인 문자까지 i가 총 1개가 있기 때문입니다.

 

 

 

 

DP를 이용해서 공식을 만들 수 있습니다.

DP[찾고자 하는 알파벳][끝] - DP[찾고자 하는 알파벳][시작 - 1]

이 공식을 이용하면, 효율적으로 답을 구할 수 있습니다.

만약 시작 순서가 0일 경우, 처음부터 검사를 하는 것이기 때문에 아무것도 빼지 않습니다.

 

 

 

---

정답 코드

const fs = require("fs");
const [str, q, ...INPUT] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
let result = "";

input = [];
INPUT.forEach((e) => {
  let temp = e.split(" ");
  temp[1] = +temp[1];
  temp[2] = +temp[2];

  input.push(temp);
});


const dp = {};

input.forEach((e) => {
  if (!dp[e[0]]) {
    let arr = [];

    for (let i = 0; i < str.length; i++) {
      let temp = i === 0 ? 0 : arr[i - 1];
      if (str[i] === e[0]) temp++;
      arr.push(temp);
    }

    dp[e[0]] = arr;
  }

  if (e[1] === 0) {
    result += dp[e[0]][e[2]] + "\n";
  } else {
    result += dp[e[0]][e[2]] - dp[e[0]][e[1] - 1] + "\n";
  }
});

console.log(result);

 

---

정답 코드 풀이

const fs = require("fs");
const [str, q, ...INPUT] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
let result = "";

input = [];
INPUT.forEach((e) => {
  let temp = e.split(" ");
  temp[1] = +temp[1];
  temp[2] = +temp[2];

  input.push(temp);
});

이 문제들을 input이라는 Array에 담는 과정입니다.

 

 

 

const dp = {};

dp 딕셔너리를 생성합니다.

 

 

 

input.forEach((e) => {

질문이 담긴 input Array를 forEach() 메소드로 접근합니다.

e는 질문의 내용이 담긴 Array로,

 

 

 

만약 질문이 위와 같은 형태라면,

e = ['a', 0, 5]로 담깁니다. 

 

e[0]은 찾고자 하는 알파벳,

e[1]은 찾기가 시작하는 순서,

e[2]은 찾기가 종료되는 순서를 의미합니다.

 

 

 

 

  if (!dp[e[0]]) {
    let arr = [];

    for (let i = 0; i < str.length; i++) {
      let temp = i === 0 ? 0 : arr[i - 1];
      if (str[i] === e[0]) temp++;
      arr.push(temp);
    }

    dp[e[0]] = arr;
  }

질문으로 받은 알파벳이 dp에 저장되어 있는지 검사합니다.

만약 dp에 아직 해당 알파벳이 없다면, 위의 코드가 실행되고, dp[찾고자 하는 알파벳]이 생성됩니다.

 

이 if문을 이용해서, 질문으로 받을 예정이 없는 알파벳까지 dp 담는 불필요한 과정을 건너뛸 수 있습니다.

 

 

 

 

  if (e[1] === 0) {
    result += dp[e[0]][e[2]] + "\n";
  } else {
    result += dp[e[0]][e[2]] - dp[e[0]][e[1] - 1] + "\n";
  }

DP[찾고자 하는 알파벳][끝] - DP[찾고자 하는 알파벳][시작 - 1]

아까 찾은 공식을 실제 코드로 작성합니다.

 

 

 

console.log(result);

마지막으로 최종 결과물을 출력하면 끝입니다.