백준 1874 - 스택 수열

코드

const fs = require("fs");
let input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => +v);
const n = input.shift();
const stack = [];
let pos = 0;
let result = "";

for (let i of input) {
  if (!stack.length || stack.at(-1) <= i) {
    for (let j = pos + 1; j <= i; j++) {
      stack.push(j);
      pos++;
      result += "+" + "\n";
    }
    stack.pop();
    result += "-" + "\n";
  } else if (stack.at(-1) > i) {
    result = "NO";
    break;
  }
}
console.log(result);

문제정리

간단하게 요약해보면 1부터 n까지의 숫자가 있는데 스택에 오름차순으로 이 숫자를 하나씩 넣을 수 있고, pop( )된 수가 수열에 들어감

예제 1번에서 수열 제일 첫번째의 수가 4인데, 4를 넣기 위해서는 stack에 1~4까지 넣기 -> 4를 pop하는 과정이 필요함

이후에는 5부터 n까지의 수를 stack에 넣을 수 있게 됨

풀이법

한마디로 내가 원하는 수를 얻기 위해서는 그 수만큼을 stack에 넣는 과정이 필요함

만약에 스택이 비었거나 , 스택에 내가 원하는 수보다 작은 수가 들어가있다면 스택에 오름차순으로 숫자를 넣어주고, pos 라는 변수를 이용해서 어느 수까지

사용했는지를 나타내주면 됨

만약에 내가 원하는 수가 스택보다 작다면 ? ex) 스택에 1 2 3 4 가 있고 내가 원하는 숫자는 3이라면 3으로 가기 위해서 4를 먼저 pop을 해줘야 하는데, pop한 숫자는 무조건 수열에 넣어야 하기 때문에 내가 원하는 수열을 만들 수 없음 - 이 경우는 안됨