[c++/프로그래머스] 뒤에 있는 큰 수 찾기

문제 링크

뒤에 있는 큰 수 찾기

풀이

stack을 이용하는 분할 상환 분석 문제.
참고는 책 알고리즘 트레이닝 136p
책에서는 보다 작으면서 가장 가까운 원소 문제로 해당 인덱스 앞쪽에 있는 가장 작은 원소를 찾는 문제인데, 이 문제는 그 반대이다.

1. 거꾸로 탐색하면서 stack이 비어있을 때는 -1이고, stack.top()이 해당 인덱스의 뒤에 있는 큰수가 된다.
2. stack의 top()이 해당 인덱스 수보다 클 때까지 pop하면 top()은 자연스레 그 큰 수가 됨
3. 계산 후 stack에 해당 인덱스를 push한다.

코드

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

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size());
    stack<int> stk;
    
    for(int i=numbers.size()-1;i>=0;i--)
    {
        while(1)
        {
            if(stk.empty())
            {
                answer[i] = -1;
                break;
            }
            if(stk.top()>numbers[i])
            {
                answer[i] = stk.top();
                break;
            }
            stk.pop();
        }
        stk.push(numbers[i]);
    }
    return answer;
}