[BOJ] 2493 : 탑 - travelbeeee

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

---

스택 Stack

● 자료구조 스택을 이용하면 입력된 값을 역으로 순회하며 문제를 해결할 수 있다.

● 현재 스택이 비어있다면, 스택에 Push

● 스택에 값이 있다면, 스택의 top과 현재 값을 비교해 현재 값보다 스택의 top이 작다면 top에 해당하는 원소는 현재 값에 신호를 보내게 되므로 답을 갱신하고 스택을 pop하고 다시 이 과정을 반복한다.

( 답 갱신하는 과정을 위해 스택에 { 값, index } 를 같이 push 해준다. )

#include<iostream>
#include<stack>

using namespace std;

int N, list[500001], ans[500001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> list[i];

	stack<pair<int, int>> s;
	for (int i = N; i > 0; i--) {
		if (s.empty()) {
			s.push({ list[i], i });
		}
		else {
			while (s.top().first < list[i]) {
				ans[s.top().second] = i;
				s.pop();
				if (s.empty())
					break;
			}
			s.push({ list[i], i });
		}
	}
	for (int i = 1; i <= N; i++)
		cout << ans[i] << ' ';
	return 0;
}

---