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

문제

 

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

프로그래머스

문제풀이

 

자신보다 뒤에 있는 숫자 중에서 자신보다 크고, 가장 가까이 있는 수를 뒷 큰 수라고 한다.

스택을 이용하여 {값, 인덱스}를 저장한다.

현재 탐색하고 있는 값이 스택의 top부분 보다 크면, 현재 값이 스택에 있는 모든 수의 뒷 큰 수가 된다.

 

반복문을 통해 스택의 top과 현재 값을 비교하여 뒷 큰 수가 되면 ansnwer에 인덱스들을 저장한다.

반복문이 종료되면 스택에 push 한다.

 

만약 뒷 큰 수가 없으면 -1을 return 해야 하므로 미리 answer을 -1로 초기화하면 편하다.

코드

#include <string>
#include <vector>
#include <stack>
#define pii pair<int, int>
using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    stack<pii>stk;
    for (int idx = 0; idx < numbers.size(); ++idx) {
        while (!stk.empty() && stk.top().first < numbers[idx]) {
            int num_idx = stk.top().second;
            answer[num_idx] = numbers[idx];
            stk.pop();
        }
        stk.push({ numbers[idx], idx });
    }

    return answer;
}