백준 2493 탑 js

2493번: 탑

이번에 풀어 볼 문제는 스택 문제입니다.

 

풀이

스택을 이용한 풀이 과정을 간단히 한다면 다음과 같습니다.

반복문을 통해 탑(tops) 중에 왼쪽부터 시작하여 오른쪽으로 탐색하겠습니다.

탐색하는 동안 스택에는 이전에 탐색했던 탑들 중 현재 탑보다 높은 탑들과 현재 탑만 존재할 수 있도록 합니다.

 

∴ 따라서

if(다음 탑의 높이 > 현재탑의 높이) => 스택에 있는 높은 탑들 중 가장 근접한 탑부터 순차적으로 다음 탑과 비교 해 봅니다. 

만약 스택에서 다음 탑보다 더 높은 탑을 발견하였다면 높은 탑의 위치가 출력값이 되는것입니다.

그렇지 않다면, 다음 탑보다 더 높은 탑은 존재하지 않기에 0을 출력하게 되는것이죠.

 

자세한 설명은 코드의 주석으로 이어가겠습니다.

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let N;

rl.on('line', function (line) {
  if(!N) {
    N = +line;
  } else {
    let tops = line.split(' ').map(n => +n);
    let answer = [];
    let stack = [];

    for(let i = 0; i < N; i++) {
      let now = tops[i]; // 현재 탑 

      // 현재 탑을 기준으로 
      // 가장 근접한 탑인 스택(stack[stack.length - 1])과 비교하여
      // 현재 탑보다 높이가 낮다면 스택에서 제거해줍니다.
      while(stack.length && tops[stack[stack.length - 1]] < now) {
        stack.pop();
      }

      if(stack.length === 0) {
        // 스택에 현재 탑보다 큰 탑이 없기때문에 0을 출력해줍니다.
        answer.push(0);
      } else {
        // 위 while문을 통해 현재 탑과 
        // 가장 근접한 탑중 높이가 더 낮은 탑은 스택에서 제거하였기 때문에
        // 남은 스택의 가장 근접한 탑(stack[stack.length - 1])인덱스에 1을 더해 출력해줍니다.
        answer.push(stack[stack.length - 1] + 1);
      }

      //현재 탑의 인덱스를 스택에 푸쉬해줍니다.
      stack.push(i);
    }

    console.log(answer.join(' '));
    rl.close();
  }
})