[BOJ 2493] 탑

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

왼쪽으로 이동하면서 자기보다 높은 송전탑의 위치를 찾는 문제이다. 문제의 조건인 n이 50만이었기 때문에 모든 경우를 다 살펴보는 경우는 최악의 경우 오름차순으로 정렬되어있을때 50*50/2 의 연산이 필요하다. 따라서 stack을 이용하여 문제를 접근할 수 있다. 

stack에 top의 위치를 비교하면서 top의 높이보다 작을때는 top의 위치를 출력하면 되고, top보다 클 경우에는 top의 높이가 자신보다 작아질때까지 pop하는 방식을 통하여 문제를 해결할 수 있다. 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define MAX_N 100
#define INF 1e8
#define MOD 1000000007
 
typedef long long ll;
 
using namespace std;
 
int n,arr[555555];
stack<pair<int,int>> st;
 
int main() {
    cin >>n;
    for(int i=1;i<=n;i++){
        cin >> arr[i];
    }
    for(int i=1;i<=n;i++){
        if(st.size() == 0){
            st.push({arr[i],i});
            cout << "0 ";
        }else{
            if(st.top().first > arr[i]){
                cout <<st.top().second<<" ";
                st.push({arr[i],i});
            }else{
                while(!st.empty()){
                    if(st.top().first < arr[i]){
                        st.pop();
                    }else{
                        break;
                    }
                }
                if(st.size() == 0){
                    cout << "0 ";
                }else{
                    cout << st.top().second<<" ";
                }
                st.push({arr[i],i});
                
            }
        }
        
    }
    return 0;
}