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

문제설명 

알고리즘

1. 수를 stack에 입력 받는다 first는 숫자, second는 인덱스 값이 된다

2. stack이 비어있지 않다면, 맨 위의값을 꺼내어 현재 숫자와 비교하여 크거나 같으면 반복문을 빠져나가고 그렇지 않으면 stack에서 뺀다 

3. 반복문을 나온 상태이면 현재 수 값과 인덱스를 저장한다 

코드

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

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

고찰

스택을 이용하여 해결할 수 있는 문제이다 

스택의 자료구조 특성상 FILO 가장 최근에 만난 큰 값을 찾을 수 있다