[백준] 탑 #2493

설명

문제를 보자마자 생각나는 건 전체를 다돌면서 푸는 O(n^2) 풀이였다.
하지만 문제 조건의 N이 500,000이었기 때문에 O(n^2)의 풀이는 포기하고 다른 풀이를 생각했다.

결국 생각해내지 못하고 다른 사람의 풀이를 참고했는데, 스택을 이용한 풀이였다.
앞에서부터 스캔하면서 현재 송전탑 높이보다 높은 송전탑의 높이를 찾을 때까지 스택에서 pop해준다. 없으면 0을 출력하고 있으면 해당 인덱스를 출력해준다.

Node.js 풀이

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

const N = Number(input[0]);
const tops = input[1].split(' ').map(Number);

const solution = (N, tops) => {
  const stack = [];
  let answer = '';
  for (let i = 0; i < tops.length; i++) {
    const height = tops[i];
    while (stack.length) {
      const top = stack.pop();
      if (height < top.height) {
        answer += top.idx + ' ';
        stack.push(top);
        break;
      }
    }
    if (stack.length === 0) {
      answer += '0 ';
    }
    stack.push({ height, idx: i + 1 });
  }
  return answer.trim();
};

console.log(solution(N, tops));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    stack<pair<int, int>> S;
    int N; cin >> N;
    for (int i=0; i<N; i++) {
        int height; cin >> height;
        while(!S.empty()) {
            if (S.top().first > height) {
                cout << S.top().second << ' ';
                break;
            }
            S.pop();
        }
        if (S.empty()) cout << 0 << ' ';
        S.push({ height, i+1 });
    }
    
    return 0;
}