3-1. 프로그래머스 - 뒤에 있는 큰 수 찾기

1. 관련 문제 🎯

문제 : 프로그래머스 뒤에 있는 큰 수 찾기 🔎
난이도 : LEVEL 2

2. 문제 소개 🧩

1️⃣ 정수로 이루어진 배열 numbers의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.

• 즉, 뒷 큰 수는 2가지 조건을 만족해야 한다.
• 1) 자신보다 뒤에 있는 숫자여야 한다.
  2) 자신보다 크면서 가장 가까이 있는 수여야 한다.

2️⃣ 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요.

3️⃣ 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

3. 문제 풀이 🖌️

뒷 큰 수는 2가지 조건을 만족해야 한다.
1️⃣ 자신보다 큰 숫자여야 한다.
2️⃣ 큰 숫자 중에서 가장 가까이 있고 뒤에 있는 수여야 한다.

해당 문제는 "자신과 가장 가까이 있는 수"라는 점에서 주목해야 한다🔥

즉, 자신과 가장 가까이 있는 수를 보장하는 stack을 사용해야 한다.
☝️stack에 대해서 간단히 요약해보자면, stack에 순서대로 배열에 넣었을 때 [1,2,3,4,5] stack의 top = 5는 바로 아래의 4(다음으로 top이 될 숫자)와 가장 가까이 있다는 것을 알 수 있다!!

• 스택에 대해서 더 자세하게 알아보고 싶다면, 아래의 링크 참고!!
  https://velog.io/@da_na/코딩테스트-스터디-01.-자료구조-문제

아래의 예시를 stack을 사용하여 해결해보자!!

• 이때, stack은 뒷 큰수를 구해야 하는 숫자들을 넣어 놓는 용도로 사용한다.
  즉, numbers의 끝까지 살펴보았을 때에도 stack에 남아 있으면 뒷 큰수를 구하지 못했으므로 -1을 반환한다.

4. 전체 코드 🔑

참고 자료 : https://jaimemin.tistory.com/2237

#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>> nums;
    
    for (int i = 0; i < numbers.size(); i++){
        while (!nums.empty()){
            pair<int, int> top = nums.top();
            
            if (top.first >= numbers[i]){
                break;
            }
            answer[top.second] = numbers[i];
            nums.pop();
        }
        nums.push({ numbers[i], i });
    }
    return answer;
}

5. 결과 🏆