C++:: 프로그래머스 <뒤에 있는 큰 수 찾기>

스택을 사용하여 접근하면 되는 문제이다. 앞에서 부터 뒤로 접근해도 되지만 필자는 뒤에서 부터 접근하는 풀이로 문제를 해결하였다.

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

vector<int> solution(vector<int> numbers)
{
    int n = numbers.size();
    vector<int> answer(n, -1);
    stack<int> st;
    for(int i=n-1;i>=0;i--)
    {
        while (!st.empty() && numbers[i] >= st.top()) st.pop();
        // 스택에 값이 있고, top이 해당 값보다 크거나 같으면 pop 해준다.
        if (!st.empty()) answer[i] = st.top();//스택에 값이 있다면
        st.push(numbers[i]);//현재값 스택에 추가
    }
    return answer;
}

인덱스를 스택에 넣어주는 방법도 존재하여 첨부한다.

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

vector<int> solution(vector<int> numbers)
{
    vector<int> answer(numbers.size(), -1);
    stack<int> st;

    for(int i=0; i<numbers.size(); i++)
    {
        while(!st.empty() && numbers[st.top()] < numbers[i])
        {
            answer[st.top()] = numbers[i];
            st.pop();
        }
        st.push(i);
    }
    return answer;
}