[BOJ] 2493번 탑 C++

문제

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

풀이

스택의 구조를 활용하여 풀 수 있는 문제다.

스택에 utility에 있는 pair를 활용하여 건물의 순서와 높이를 같이 스택에 저장한다.

높이의 최대 값이 100,000,000이므로 스택의 맨 처음 값의 높이를 100,000,001로 주어 최대 값을 설정해서 스택이 비어 비정상적인 접근을 하게 될 경우를 제외한다.

그 이후에 들어오는 건물의 높이를 비교하여 스택의 top의 높이보다 작으면 top의 건물의 순서를 출력하고

만약 크다면 스택의 top의 높이 값이 더 클 때까지 pop연산을 해준다.

소스코드

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

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

    stack<pair<int,int>> tower;

    int n,a;
    cin >> n;

    tower.push({100000001,0});
    
    for(int i=1;i<=n;i++){
        cin >> a;
        while(tower.top().first<a)
            tower.pop();
        cout << tower.top().second << " ";
        
        tower.push({a,i});
    }
}