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

✅ LV.3

✏️ 1차 솔루션

⭐️ 이분 탐색

upper_bound 로 현재 위치부터 배열 끝까지 범위 중에 현재 위치 값보다 큰 값이 처음 등장하는 인덱스의 배열값을 answer에 저장

🚨 1차 trouble

반례도 통과하는데 왜 틀렸는지 모르겠다

✏️ 최종 솔루션

⭐️ Stack
맨 뒤부터 stack에 넣어가며 가장 큰 뒷 수 탐색

1. 맨 뒷자리는 stack 에 비어있기 때문에 answer 에 -1 저장하고 앞자리의 가장 큰 뒷수가 될 수 있기 때문에 현재 값 stack 에 push
2. stack 의 top 이 가장 가까운 수인데 현재 자리 값보다 top 이 같거나 작으면 더 먼 수 중에 큰 값을 찾을 때까지 pop
3. 더 먼 수 찾으면 이를 answer 에 저장하고 현재 값을 stack 에 push
   ❗️ 탐색 과정에서 pop 한 값들이 현재 값보다 작고 다음 탐색할 위치보다 멀기 때문에 pop 한 값들을 기록할 필요 없음
4. 더 먼 수가 존재하지 않으면 stack 이 empty 가 되므로 1번과 같이 answer 에 -1 저장하고 현재 값 stack 에 push

✏️ 최종 code

#include <stack>
#include <vector>

using namespace std;

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