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(' '));