백준 2493번 : 탑

문제 링크 입니다

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

2493번: 탑

 

 

스택을 이용하는 문제였는데 잘 한건지 모르겠네요.

 

처음에 그래서 스택을 무조건 써야겠다고 생각해서 

#include<iostream>
#include<stack>
 
using namespace std;
 
int main() {
    ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
    int n;
    cin >> n;
    stack<pair<int, int>> s;
    stack<pair<int, int>> s2;
    stack<int> ans;
    
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        s.push(make_pair(k, i));
    }
 
    for (int i = 0; i < n; i++) {
        int num;
        num = s.top().first;
        
        s.pop();
        
        while (1) {
 
            if (s.empty()) {
                ans.push(0);
                break;
            }
 
            else if (s.top().first>= num) {
                ans.push(s.top().second);
                break;
             }
 
            s2.push(make_pair(s.top().first, s.top().second));
            s.pop();
        }
 
        for (int i = 0; i < s2.size(); i++) {
            s.push(make_pair(s2.top().first, s2.top().second));
            s2.pop();
        }
    }
 
    for (int i = 0; i < n; i++) {
        cout << ans.top() << " ";
        ans.pop();
    }
}

이런식으로 반복문을 여러개 썻더니 

 

이런 결과가 나왔고

 

수정한 코드가

 

#include<iostream>
#include<stack>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    pair<int, int> p[500000];
 
 
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        p[i].first = i;
        p[i].second = k;
 
    }
    stack<int> ans;
    int a;
    for (int i = n ; i >= 1; i--) {
        a = i - 1;
        while (1) {
            if (p[i].second <= p[a].second) {
                ans.push(p[a].first);
                break;
            }
            a--;
            if (a == -1) {
                ans.push(0);
                break;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans.top() << " ";
        ans.pop();
    }
}