[Gold 5] 2493 탑

https://www.acmicpc.net/problem/2493

 

이 문제는 오큰수 문제와 유사한 방식으로 해결하였다.

스택을 사용해서 문제를 접근하였다.

 

오큰수는 뒤에서부터 스택에 값을 넣고

스택의 top이 현재 검색할 값보다 클때까지 스택을 pop한다.

이후, 스택의 top을 오큰수로 지정한 것을 알 수 있다.

 

위 방식을 반대로 생각하면

배열의 앞에서부터 스택의 요소로 집어 넣으면

배열의 가장 앞에 있는 요소는 스택이 비어 있으므로 0이 될 것이다.

이후 스택에 가장 앞에 있는 요소를 넣고, 그 다음 배열의 요소를 통해 

스택의 top과 비교해 스택의 top이 작으면 스택에서 pop한다.

 

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

int N;
int tops[500001];
stack<pair<int,int>> s;
int answer[500001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>N;
    
    for(int i = 0;i<N;i++)
        cin>>tops[i];
    
    // 6 9 5 7 4
    // 주어진 순서의 반대 방향으로 신호 발사
    for(int i = 0;i<N;i++){
        while(!s.empty() && s.top().first <= tops[i])
            s.pop();
        
        if(s.empty())
            answer[i] = 0;
        else
            answer[i] = s.top().second;
        
        s.push({tops[i],i + 1});
    }
    
    for(int i = 0;i<N;i++)
        cout<<answer[i]<<' ';

}