[스택]백준2493번 탑

백준2493번

탑

스택을 이용하면 매우 간단하게 풀리는 문제였다.

들어오는 탑의 높이들을 차례로 스택에 넣고, 다음과 같은 과정을 수행한다.

스택이 비어있는 경우

내 왼쪽으로는 아무도 없거나 나보다 높은 탑이 없다는 뜻이기 때문에 스택에 push 한다.

스택의 top이 나보다 클 경우

내가 발사한 레이저 신호가 스택의 top에 위치한 탑에 막힌다는 뜻이기 때문에 스택의 top에 위치한 탑의 순서번호를 내 정답으로 기록한 뒤 스택에 push 한다.

스택의 top이 나보다 작을 경우

내가 발사한 레이저가 스택의 top에 위치한 탑에는 막히지 않는다는 뜻이다. 따라서 나 이후로 들어오는 탑들의 레이저도 나에게 막히거나 넘는다는 뜻이기 때문에, 스택 안에서 나보다 높은 애가 나올 때까지 스택을 pop 한다.

만약 나보다 큰 탑이 나올 경우 위의 <스택의 top이="" 나보다="" 클="" 경우=""> 의 과정을 수행한다.

주의해야 할 점은, 스택의 top이 나보다 큰 경우에도 나를 스택에 push 해야 한다는 점이다.

이후에 들어오는 탑이 나보다 작을 경우가 존재하기 때문이다.

#include <iostream>
#include <stack>

using namespace std;
int answer[500001];
int main(){
    int N;
    cin >> N;
    int copyN = N;
    stack<pair<long long,int> > s;
    int idx = 1;
    while(N--){
        long long tmp;
        cin >> tmp;
        if(!s.empty()){
            if(s.top().first > tmp){
                answer[idx-1] = s.top().second;
                s.push(make_pair(tmp,idx));
            }
            else{
                while(!s.empty() && s.top().first < tmp){
                    s.pop();
                }
                if(!s.empty()) answer[idx-1] = s.top().second;
                s.push(make_pair(tmp,idx));
            }
        }
        else s.push(make_pair(tmp,idx));
        
        idx ++;
    }
    
    for(int i=0;i<copyN;i++){
        cout << answer[i] << " ";
    }
    
    
    return 0;
}