[C++/BOJ] 2493 : 탑 (Stack)

 

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

 

백준 골드5

쉽다고 생각하면서 2중반복문으로 썼는데.. 시간초과 ㅋㅋ

스택을 사용해서 낮은 건 pop하고, 수신 탑만 남겨두어야 한다

 

 

나의 풀이

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

int main() // 이중반복문 쓰면 시간초과남
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	int height;
	stack<pair<int,int>> st; // 인덱스, 높이
	cin >> n;
	for (int i = 1; i <= n; ++i){
		cin >> height;
		while(!st.empty()){
			if(st.top().second < height) st.pop();
			else {
				cout << st.top().first <<" ";
				st.push({i, height});
				break;
			}
		}
		if(st.empty()) {
			cout << 0 <<" ";
			st.push({i, height});
		}
	}
}