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

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

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

using namespace std;

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

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

    return answer;
}

---

📝 풀이

하나의 숫자 정보를 key가 숫자고 value가 인덱스인 pair로 stack에 저장합니다.

stack이 비어있지 않고 현재 숫자가 stack의 top보다 크면 현재 숫자는 stack의 top 숫자의 뒷 큰수가 됩니다.

이를 answer에 추가하고 stack은 pop을 합니다.

이 과정에서 뒷 큰수가 없는 수는 answer에 추가되지 않기 때문에 answer에는 -1로 초기화를 합니다.