문제

Code

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

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

    stack<pair<int,int>> S;
    vector<int> V;
    int N,input;

    cin >> N;

    for(int i=0;i<N;i++)
    {
        cin >> input;
        if(S.empty())
        {
            V.push_back(0);
            S.push({i+1,input});
        }
        else if(S.top().second < input)
        {
            int size = S.size();
            for(int j=0;j<size;j++)
            {
                S.pop();
                if(S.empty())
                {
                    V.push_back(0);
                }
                else
                {
                    if(S.top().second > input)
                    {
                        V.push_back(S.top().first);
                        break;
                    }
                }
            }
        S.push({i+1,input});
        }else{
            V.push_back(S.top().first);
            S.push({i+1,input});
        }
    }
    for(auto a : V)
        cout << a << ' ';
}

• 시간초과를 주의해야 하는 문제이다
• 각 입력 뒤에 요소들과는 무관하므로 입력받으면서 처리해야한다
• input을 받았을 때 S.top()과 비교하여 S.top() > input 이 될 때 까지 S.pop()을 해야함
• stack을 인덱스와 요소 둘다 저장하기 위해 pair을 사용

    stack<pair<int,int>> S;
    S.push({i,input});
    S.top().first  // 인덱스
    S.top().second // 값