[문제]
https://www.acmicpc.net/problem/2493
2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1
www.acmicpc.net
[풀이]
스택
[코드]
#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>> S;
vector <int> V;
int cnt = 1;
while(n--){
int t;
cin >> t;
if(S.empty()) {
V.push_back(0);
}
else {
if(S.top().first >= t) {
V.push_back(S.top().second);
}
else {
while(!S.empty()) {
if(S.top().first >= t){
V.push_back(S.top().second);
break;
}
S.pop();
}
if(S.empty()) V.push_back(0);
}
}
S.push({t, cnt++});
}
for(int i=0; i<V.size(); i++){
cout << V[i] << " ";
}
}