[프로그래머스/C++]Lv.2 - 뒤에 있는 큰 수 찾기

문제 링크

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

시도한 방법

처음엔 이중for문으로 했었다. 당연히 시간 초과가 났다.

다른 사람의 풀이

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

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

다른 사람의 풀이 해석

answer를 numbers의 size만큼 초기화 한다.
for문을 거꾸로 돌리면서 while문을 사용한다.
스택이 비어있으면 answer[i]에 -1을, 스택의 top이 numbers[i]보다 크면 answer[i]에 스택의 top을 넣는다.
둘 다 아니라면 스택을 한번 pop한다.
즉 스택의 top이 현재 숫자보다 큰게 나올 때 까지 스택을 비워가다가 있으면 그걸 넣고 끝까지 없으면 현재 가장 큰 수 이므로 -1을 넣는다.
while을 나오면 현재 숫자를 스택에 넣어준다.
분할상환분석 알고리즘이라고 한다.
https://velog.io/@slow_cosmos/c프로그래머스-뒤에-있는-큰-수-찾기