BOJ2493 탑(C++)

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

문제 태그 : 스택

사고 흐름

---

스택이라는걸 알고 풀기 시작했지만...

앞에서부터 하나씩 검사하며 코드 짜다가 머리가 뜨거워졌다.

뒤에서부터 보니 아이디어도 쉬워지고 구현도 쉬워졌다.

뒤에서부터 하나씩 가져와 push하고, 현재 탑이 stack의 top보다 높다면

현재 탑보다 높은 탑 찾을 때까지 pop. ans 배열에 현재 탑 인덱스 기록

이러다보면 마지막에 스택에 남는 탑들은 결국 0이므로 뭐 안 해도 됨

---

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

/*
* 뒤에서부터 보면 쉬움
*/

int n;
int arr[500000];
int ans[500000];
stack<pair<int, int>> s;

void solve() {
    for (int i = n - 1; i >= 0; --i) {
        if (s.empty()) {
            s.push({ arr[n - 1], n - 1 });
        }
        else {
            if (arr[i] > s.top().first) {
                while (!s.empty() && arr[i] > s.top().first) {
                    ans[s.top().second] = i + 1;
                    s.pop();
                }
                s.push({ arr[i], i });
            }
            else {
                s.push({ arr[i], i });
            }
        }
    }
}

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

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    solve();

    if (s.size() == n) {
        cout << 0;
    }
    else {
        for (int i = 0; i < n; ++i) {
            cout << ans[i] << ' ';
        }
    }

}