[JS] 탑 문제

문제

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

 

풀이

이 문제를 처음 풀때는 순회 방식을 이용해 풀이했지만, 시간초과가 발생했다.

 

이 문제를 풀려면 스택 알고리즘을 이용해야 한다. 스택에 차례대로 타워들을 넣어야 하는데, 이때 기존 스택 마지막에 있던 타워보다 작은 타워는 스택에 들어가지 않고 바로 수신을 받는(스택에 있는 타워) 위치 번호를 답으로 저장한다. 만약 현재 타워가 더 크다면 기존에 있던 타워들 중 현재 타워보다 작은 타워들을 모두 pop해준다. 이때 중의해야할 것은 현재 타워보다 작은 타워들만 없애줘야한다. 이유는 다음에 올 타워들 중 현재 타워보다는 크고 기존 스택의 타워보다 작은 타워가 올 수 있기 때문이다.

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => e);

const n = input.shift();
const arr = input[0].split(' ').map(Number);
const answer = Array.from({ length: n }, () => 0);
const stack = [];

for (let i = 0; i < arr.length; i++){
  const tower = [arr[i], i + 1];

  if (!stack.length) {
    stack.push(tower);
  }
  else {
    if (stack[stack.length - 1][0] < tower[0]) {
      while (stack.length) {
        if (stack[stack.length - 1][0] >= tower[0]) break;
        else stack.pop();
      }
      answer[i] = stack.length ? stack[stack.length - 1][1] : 0;
      stack.push(tower);
    }
    else {
      answer[i] = stack.length ? stack[stack.length - 1][1] : 0;
      stack.push(tower);
    }
  }
}

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