[백준] 2439 탑 - javascript

📌 문제

https://www.acmicpc.net/problem/2493

📌 풀이

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

let num = Number(input[0]);
let top = new Array(num);
let ans = new Array(num);
top = input[1].split(" ").map(Number);
let stack = [];

for (let i = 0; i < num; i++) {
  if (stack.length === 0) {
    ans[i] = 0;
    stack.push([top[i], i + 1]);
  } else {
    while (stack.length !== 0) {
      let v = stack.pop();
      if (v[0] > top[i]) {
        ans[i] = v[1];
        stack.push([v[0], v[1]]);
        stack.push([top[i], i + 1]);
        break;
      }
    }
    if (stack.length === 0) {
      ans[i] = 0;
      stack.push([top[i], i + 1]);
    }
  }
}
console.log(ans.join(" "));

✔ 알고리즘 : 스택

✔ 스택에 값을 넣을때는 [탑의높이, 탑의 index]로 넣는다

✔ 스택이 비어있는 경우는 현재탑보다 왼쪽에 큰탑이 없는 경우이므로 ans에 0넣고 스택에 push

✔ 스택이 비어있지 않은 경우는 스택의 탑이 현재 for문을 돌고있는 top[i]보다 클 때까지 pop

✔ pop한 탑의 index가 현재 for문을 돌고있는 i번째 탑의 레이저가 부딪히는 탑이므로 pop한 탑의 index를 ans[i]에 저장

✔ 다음 top으로 넘어가기전에 pop했던 탑의 정보를 stack에 push하고 현재 top의 정보도 stack에 push

✔ pop을 계속해서 조건을 만족하지 못하고 top.length가 0이 되는 경우는 왼쪽에 자신보다 큰 탑이 없는 것이므로 ans[i]=0 처리하고 stack에 push

✔ 난이도 : 백준 기준 골드5