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

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

프로그래머스

 

해결 방법

뒤에 나보다 큰 수를 for문으로 찾으면 시간초과 문제가 발생한다. 적절한 자료구조를 이용해 빨리찾는 것이 핵심.

• 스택을 만들고, 내 앞에 있는 숫자보다 작으면 그냥 넣는다. 만약 [9,3,2,5] 가 있다면 9 > 3 > 2 까지는 그대로 스택에 넣는다. 참고로 스택에는 index값을  넣는다. 
• 만약 앞에 넣은  숫자보다 큰 숫자가 나왔다면,이제 작업을 시작할 때이다. 큐에서 하나씩 빼면서, 나자신보다 작은지 검사하여 만약 나보다 작다면 정답을 적어주고 스택에서 제거한다. 
• 나 자신도 검사를 받아야하므로, 스택에 넣어준다.

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

using namespace std;

vector<int> solution(vector<int> numbers) {
    stack<int> s;
    vector<int> answer(numbers.size(), -1);
    
    
    for(int i=0; i<numbers.size(); i++){
       //스택에 있는 값이 나보다 크다면 스택에 넣고 패스
        if(s.empty() || numbers[s.top()] > numbers[i]){
            s.push(i);
            continue;
        }
        
        while(!s.empty()){
            //나보다 큰 놈이 나오기전까지 뽑아서 처리
            if(numbers[s.top()] >= numbers[i])break;
            answer[s.top()] = numbers[i];
            s.pop();
        }
        
        s.push(i);
    }
    
    return answer;
}