[백준/C++] 2493번 탑

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

2493번: 탑

 

 

문제풀이

 

스택을 사용하여 i번째 탑의 높이보다 크고 다른 탑에 의해 가려지지 않은 탑들만 스택에 남겨야한다. (i번째 탑에 서서 왼쪽의 탑들을 보았을 때 보이는 탑들)

 

 

코드

#include <iostream>
#include <stack>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N;
    cin>>N;

    pair<int, int> tower[N];
    for(int i=0; i<N; i++){
        int height;
        cin>>height;
        tower[i] = {i+1, height};
    }

    stack<pair<int,int>> s;
    for(int i=0; i<N; i++){
        while(!s.empty() && s.top().second < tower[i].second){
            s.pop();
        }

        if(s.empty()){
            cout<<0<<" ";
        }
        else{
            cout<<s.top().first<<" ";
        }

        s.push(tower[i]);
    }

    return 0;
}

 

 

결과