이번 문제는 스택을 활용해서 해결하는 문제였다. 이중 for문을 통해서도 해결할 수는 있지만 시간 제한에 걸리게 되므로 스택을 통해 해결해야 한다.
본인은 스택으로 해결하기 전에 이중 for문으로 한번 구현해 보았고 당연히 시간 제한에 걸렸고, 스택으로 다시 한번 풀어보았다.

• n과 배열을 입력받는다.
• 배열을 뒤에서부터 검사한다. 스택이 비어있지 않고 스택의 top이 배열의 수보다 작거나 같다면 스택을 pop해준다. 이 과정은 while문을 통해 스택이 empty되거나 스택의 top이 배열의 수보다 클때까지 반복된다.
• 스택이 empty라면 결과 배열에 -1을 넣어준다.
• 스택에 배열의 수를 push해준다.
• 이 과정을 배열의 마지막 인덱스에서 첫번째 인덱스까지 반복한다.

Code

#include <iostream>
#include <stack>
#define MAX 1000001
using namespace std;

int n;
int arr[MAX];
int result[MAX];
stack<int> st;

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
}

void Solution(){
    for(int i=n-1; i>=0; i--){
        while(!st.empty()&&st.top()<=arr[i]){
            st.pop();
        }
        if(st.empty()){
            result[i]=-1;
        }
        else{
            result[i]=st.top();
        }
        st.push(arr[i]);
    }
    for(int i=0; i<n; i++){
        cout<<result[i]<<" ";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}