[boj] 백준 2493 탑 - stack

[문제]

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

2493번: 탑

 

[풀이]

본인의 바로 왼쪽에 있는 탑부터 비교하도록 하기 위해 stack을 이용한다. 현재 탑의 높이보다 크면 출력, 작으면 pop()을 해주고, stack이 비면 왼쪽에 있는 탑들 중 신호를 받을 탑이 없다는 것이므로 0을 출력한다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace::std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    stack<pair<int, int>> top;
    cin >> n;

    int height;
    for(int i=1; i<=n; i++){
        cin >> height;
        while(!top.empty()){
            if(top.top().second > height){
                cout << top.top().first << " ";
                break;
            }
            top.pop();
        }

        if(top.empty())
            cout << "0 ";

        top.push({i, height});

    }

}