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

문제 설명

배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이에 있는 수를 뒷 큰수라고 할 때, 모든 원소들에 대한 뒷 큰수를 담을 배열을 return

 

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

프로그래머스

 

문제 풀이법

stack을 사용하면 쉽게 풀 수 있다

 

주어진 배열의 맨 끝에서부터 탐색하는데, 만일 stack이 비어있다면 뒷 큰수가 없다는 뜻이므로 answer에 -1을 담고 stack에 자신을 담는다

비어있지 않다면 스택이 빌때까지 탐색을 하는데 이때, stack의 top이 자기 자신보다 작거나 같으면은 pop 해주면서 재귀를 계속 돌고, 크면은 재귀를 빠져나가게 한다

재귀를 빠져나간 이후 stack이 비어있으면, 이 역시 뒷 큰수가 없다는 뜻이므로 answer에 -1을 담고 자기 자신을 stack에 담는다

비어있지 않으면 뒷 큰수가 있다는 뜻이므로, 스택의 top을 answer에 담고 자기 자신을 스택에 담는다

 

이후 answer를 reverse해서 return 해준다

 

소스 코드

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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