백준 21318 피아노 체조

문제

솔직히 시간 제한만 없으면 간단하게 풀 수 있는 브론즈 문제이다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const n = +inputs[0];
const sheet = [0, ...inputs[1].split(" ").map(Number)];
const questions = inputs.slice(3);
 
questions.forEach((q) => {
  const [x, y] = q.split(" ").map(Number);
  let cnt = 0;
  for (let i = x; i < y; i++) {
    if (sheet[i] > sheet[i + 1]) {
      cnt++;
    }
  }
  console.log(cnt);
});
 

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const n = +inputs[0];
const sheet = [0, ...inputs[1].split(" ").map(Number)];
const questions = inputs.slice(3);
const dp = new Array(n + 1).fill(0);
 
let acc = 1;
for (let i = n - 1; i > 0; i--) {
  if (sheet[i] > sheet[i + 1]) {
    dp[i] += acc;
    acc++;
  } else {
    dp[i] = acc - 1;
  }
}
 
questions.forEach((q) => {
  const [x, y] = q.split(" ").map(Number);
  console.log(dp[x] - dp[y]);
});
 

시간을 줄이고자 처음에 해당 i인덱스에서 끝까지 해서 가지는 실수의 수를 기록했다. 이게 dp긴 아닌데,,, 임의의 배열 만들 때는 나도 모르게 dp라는 이름으로 짓게 되는것 같다. 그래서 매 질문마다 계산하는 것이 아니라 처음에 한번 계산한 것을 계속 최대실수의 차이로 출력하도록 했는데 결과는?

이렇게 해도 시간 초과가 뜬다.. 원인을 살펴보니 forEach문으로 매번 출력을 조지는게 문제였던 것 같다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const n = +inputs[0];
const sheet = [0, ...inputs[1].split(" ").map(Number)];
const questions = inputs.slice(3).map((q) => q.split(" ").map(Number));
const dp = new Array(n + 1).fill(0);
 
let acc = 1;
for (let i = n - 1; i > 0; i--) {
  if (sheet[i] > sheet[i + 1]) {
    dp[i] += acc;
    acc++;
  } else {
    dp[i] = acc - 1;
  }
}
 
let result = "";
for (const [x, y] of questions) {
  result += `${dp[x] - dp[y]}\n`;
}
console.log(result);

이래 고치니 또 된다… 킹받네 출력까지 시간을 고려하는건 생각을 못했는데 머리가 띵했다. 앞으로는 출력도 조금 더 빠르게 할 수 있도록 신경을 써야 할 것 같다..