뒤에 있는 큰 수 찾기(10분)

https://school.programmers.co.kr/learn/courses/30/lessons/154539

구현 아이디어 3분 구현 7분

풀이

1. numbers의 뒤 원소부터 큐에 담는다.
2. 큐에서 원소를 하나씩 꺼내며 뒤에 있는 큰 수를 찾는다.

• 스택의 top에 있는 원소가 꺼낸 원소보다 크다면 top의 원소가 뒤 큰 수이다.
• 스택의 top에 있는 원소가 꺼낸 원소보다 작다면 스택에서 계속 꺼내본다.
• 스택이 empty 상태라면 뒤 큰 수가 없기에 -1을 대입한다.

#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

vector<int> solution(vector<int> numbers) {
    int N = numbers.size();
    
    vector<int> answer(N);
    vector<int> V(N);
    queue<int> Q;
    stack<int> S;
    
    for(int i = N - 1; i >= 0; --i)
        Q.push(numbers[i]);
    
    for(int i = N - 1; i >= 0; --i)
    {
        int cur = Q.front();
        Q.pop();
        
        if(!S.empty())
        {
            while(!S.empty())
            {
                int pick = S.top();
                if(pick > cur)
                {
                    V[i] = pick;
                    break;
                }
                else S.pop();
            }
        }
        if(S.empty()) V[i] = -1;
        
        S.push(cur);
    }
    
    for(int i = 0; i < N; ++i)
        answer[i] = V[i];
    
    return answer;
}