본문 바로가기
알고리즘 문제/자료구조

[개쉬운 풀이] 백준 2493 탑

by odaebum 2024. 11. 10.
728x90

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;

const int MAX = 500001;

int n;
int tower[MAX];
vector<int> stack;

void init(){
    memset(tower, 0, sizeof(tower));
}
void input(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> tower[i];
    }
}

void print(){
    if(stack.empty()) cout << 0 << " ";
    else{
        cout << stack.back() + 1 << " ";
    }
}

void sol(){
    for(int i = 0; i < n; i++){
        int tmp = tower[i];
        if(stack.empty()) {
            stack.push_back(i);
            cout << 0 << " ";
        }
        else{
            while(!stack.empty()){
                if(tower[stack.back()] > tmp) {
                    print();
                    break;
                }
                else{
                    stack.pop_back();
                }
            }
            if(stack.empty())cout << 0 << " ";
            stack.push_back(i);
        }
    }
}

int main(){
    input();
    sol();

    return 0;
}
728x90