프로그래머스 (C/C++) 154539 : 뒤에 있는 큰 수 찾기

 

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=cpp

프로그래머스

 

---

풀이

주어진 배열의 뒤에서부터 탐색하며 스택에 값을 저장

현재 인덱스의 값 < 뒤의 인덱스 값(스택에 저장된 값) 일 때까지 스택의 원소를 제거한다면, 현재 인덱스보다 크고 가장 가까이에 있는 뒤에 있는 큰 수를 구할 수 있음

이 때 스택이 비어있다면 현재 인덱스가 뒤를 탐색했을 때 가장 큰 값이므로 -1 저장

---

코드

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

using namespace std;

vector<int> solution(vector<int> numbers) {
    int size = numbers.size();
    vector<int> answer(size);
    stack<int> bigValue;
    
    // init
    answer[size - 1] = -1;
    bigValue.push(numbers[size - 1]);
    
    // 뒤에서부터 탐색
    for (int i = size - 2; i >= 0; i--) {
        
        // 현재 원소보다 작은 뒤에 있는 숫자를 스택에서 제거
        while (bigValue.size() && numbers[i] >= bigValue.top())
            bigValue.pop();
        
        // 스택이 비어있다면 -1, 스택에 값이 있다면 해당 값
        answer[i] = bigValue.empty() ? -1 : bigValue.top();

        // 현재 자리의 원소 스택에 저장
        bigValue.push(numbers[i]);
    }
    return answer;
}