[백준,c++] 2493번 - 탑

문제

2493번: 탑

 

코드

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    stack<pair<int,int>>st; // {탑 번호, 높이}
    
    for(int i=0; i<N; i++){
        int height; cin>>height;

        while(!st.empty()){
            if(st.top().second>height){
                cout<<st.top().first<<' ';
                break;
            }
            st.pop();
        }
        if(st.empty()) cout<< 0 <<' ';
        st.push({i+1,height});
        
    }
}

 

풀이

stack에 {탑 번호, 높이} 형식으로 저장을 하기 위해 pair 타입으로 선언합니다.

송신탑을 입력받을 때마다 stack을 찾는데, 만약 현재 스택이 비어있지 않다면 현재 송신탑의 높이보다 큰 높이가 나올 때까지 스택을 비워갑니다. 만약 현재 송신탑보다 큰 높이를 발견했다면 그 송신탑은 지우지 말아야 합니다.

그 후, while문을 빠져나왔을 때 스택이 비어있다면 현재 송신탑보다 높은 탑이 없다는 말이 되기에 0을 출력합니다.

그리고 공통적으로 현재의 송신탑은 스택에 넣어줍니다.

제일 처음 풀었을때는 아래와 같이 조금 더럽게 풀었었습니다.

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    stack<pair<int,int>>st; // {탑 번호, 높이}
    
    for(int i=0; i<N; i++){
        int height; cin>>height;
        if(i==0){
            cout<<0<<' ';
            st.push({i+1, height});
            continue;
        }
        while(!st.empty()){
            if(st.top().second>height){
                cout<<st.top().first<<' ';
                st.push({i+1, height});
                break;
            }
            else{
                bool flag = false;
                while(!st.empty()){
                    if(st.top().second<height) st.pop();
                    else{
                        flag = true;
                        cout<<st.top().first<<' ';
                        break;
                    }
                }
                if(!flag) cout<<0<<' ';
                st.push({i+1, height});
                break;
            }
        }
        
    }
}