BOJ 1392 - 노래 악보

문제

각 노래의 재생 시간이 주어질 때, Q개의 시각에 어떤 노래가 재생 중인지 출력하라.

입력

첫째 줄에 N과 Q, 이후 N줄에 각 노래의 재생 시간, Q줄에 질의 시각이 주어진다.

출력

각 질의에 대해 해당 시각에 재생 중인 노래 번호를 출력한다.

예제

입력	출력
`3 2` `5` `8` `3` `0` `10`	`1` `3`

풀이

각 노래의 시간만큼 배열을 확장하여 시각에서 노래 번호로의 직접 매핑 테이블을 만든다.

각 노래의 재생 시간만큼 노래 번호를 배열에 반복 추가한다
질의 시각을 인덱스로 배열에서 직접 조회한다

핵심 아이디어: 시간을 배열 인덱스로 매핑하면 각 질의를 O(1)에 응답할 수 있다.

코드

const solution = (input) => {
  const [N, Q] = input[0].split(" ").map((v) => +v);
  const arr = [];
  for (let i = 1; i < N + 1; i++) {
    time = +input[i];
    for (let j = 0; j < time; j++) arr.push(i);
  }
  const sb = [];
  for (let i = N + 1; i < N + 1 + Q; i++) sb.push(arr[input[i]]);
  return sb.join("\n");
};
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));

복잡도

시간: O(N x T + Q)
공간: O(N x T)

문제