[BOJ] 2493 탑 (반례 포함) | 스택

Problem | 탑

😰 처음 문제 풀이

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let len = Number(input[0]);
// 탑의 길이
let top = input[1].split(" ");
// top에 들어온 배열들

let stack = [];
let answer=new Array(len).fill(0);

for (let i = len - 1; i >= 0; i--) {
  if (stack.length != 0 && parseInt(top[stack[stack.length - 1]]) < parseInt(top[i])) {
    while(stack.length){
      let x=stack.pop();
      answer[x]=i+1;
    }
  }
  stack.push(i);
}

console.log(answer.join(' '));

💡 해결 - 최종코드

위와 같은 코드를 사용하면,
5 4 6 2 3 라는 입력 값에 [0,1,1,3,3] 이라는 답이 나온다. 6이 가장 큰수여서 0이 나와야하는데 전체 pop 해주어 1이 나오는 반례가 존재한다.

내림차순으로 된 스택에 어긋나는 수 하나라도 큰 것이 들어오면 전체 스택을 pop() 해주었는데 들어오는 수보다 작은 수만 pop() 해준다.

let fs = require("fs");
// let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let input = fs.readFileSync("./input.txt").toString().split("\n");

let len = Number(input[0]);
// 탑의 길이
let top = input[1].split(" ");
// top에 들어온 배열들

let stack = [];
let answer=new Array(len).fill(0);

for (let i = len - 1; i >= 0; i--) {
  if (stack.length != 0 && parseInt(top[stack[stack.length - 1]]) < parseInt(top[i])) {
    while(parseInt(top[stack[stack.length - 1]]) < parseInt(top[i])){
      let x=stack.pop();
      answer[x]=i+1;
    }
  }
  stack.push(i);
}

console.log(answer.join(' '));