[백준] 2493 탑

2493번: 탑

 

www.acmicpc.net

스택을 이용해서 푸는 문제이다. 스택 관련 문제들을 많이 안풀어봐서 그런지 생각보다 오래걸렸다. 스택 관련 문제들을 많이 풀어봐야 할 것 같다.

풀이

현재 탑의 높이를 tmp라고 하자.

1. stack이 비어있으면 0을 출력하고 tmp을 push.
2. stack이 비어있지 않은 경우 stack.top() > tmp이 될 때까지 pop한 뒤 stack.top()에 대응하는 탑의 번호를 출력하고 tmp를 push.

코드

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    stack<pair<int, int>> s;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        while (!s.empty()) {
            if (s.top().first > tmp) {
                cout << s.top().second << ' ';
                break;
            }
            s.pop();
        }
        if (s.empty()) cout << 0 << ' ';
        s.push({ tmp, i });
    }
    cout << '\n';
    return 0;
}