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

문제

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

프로그래머스

stack 을 이용해 자신의 뒤에 있으면서 가장 가까운 큰 수를 찾는 문제였다.

 

문제 풀이

처음에는 완전탐색을 이용해 풀었는데 4개의 케이스에서 시간 초과가 나왔고, 입력값이 최대 100만인 상황에서 break 조건을 걸어서 시간 초과를 해결해도 출제 의도와는 다른 것 같아서 다른 방법으로 풀었다.

 

 자신의 뒤에서 가장 가까운 큰 수를 찾는 문제였기 때문에 stack을 사용했다. numbers의 뒤에서부터 stack의 값들 중 큰 값이 나올 때까지 pop 해주고, 마지막에 자기 자신을 push해줬다. 

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

using namespace std;

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

    return answer;
}