탑 (feat. 백준, 2493번)

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

2493번: 탑

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, i;
    stack<pair<int, int>> ans;
    cin >> N;
    for(register int n = 0, v; n < N; ++n){
        cin >> v;
        while(!ans.empty()){
            if(v <= ans.top().second){
                cout << ans.top().first << " ";
                break;
            }
            ans.pop();
        }
        if(ans.empty())
            cout << 0 << " ";
        ans.push(make_pair(n + 1, v));
    }
    return 0;
}
// *&)*@*

 

1. 시간 초과로 인해 꽤나 시간이 걸렸습니다.
2. stack의 마지막 높이보다 더 높은 값을 입력받은 경우, stack의 마지막 값은 입력받은 값으로 swap될 수 있습니다. 단, 값이 변경되는 것일뿐 인덱스는 증가되어야 합니다. (그래서 pair를 사용하였습니다.)
3. 반대로 stack의 마지막 높이보다 더 낮은 값을 입력받은 경우, stack에 입력받은 값을 쌓을 수 있어야 합니다.