탑

백준 2493번: 탑

아이디어

스택 2개를 만들고 1번 스택에 모두 push한다. 1번 스택의 top과 2번 스택의 top을 비교한다. 스택 2번의 top이 더 크거나 스택 2번이 비어있을 경우 1번 스택에서 pop해서 2번 스택에 push한다. 1번 스택의 top이 더 큰 경우 2번 스택에서 pop하면서 해당 탑이 위치한 인덱스에 1번 스택의 size를 기록한다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n;
	cin >> n;
	stack<pair<int, int>> S1, S2;
	int ans[n] = {};
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		pair<int, int> p = {x, i};
		S1.push(p);
	}
	
	while (S1.size()) {
		while (S2.size() && S1.top().first > S2.top().first) {
			ans[S2.top().second] = S1.size();
			S2.pop();
		}
		S2.push(S1.top());
		S1.pop();
	}
	
	for (int i : ans) {
		cout << i << ' ';
	}
    return 0;
}

여담

C++로 바꾼 이유: 멋있어서
STL 사용법에 대해 알아가는중