99클럽 코테 스터디 1일차 TIL, 프로그래머스 / 뒤에 있는 큰수

 

 

 

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

using namespace std;

int total_num;

int find(int originIdx, int *numbers)
{
    int answer = -1;
    
    if (originIdx == total_num - 1) 
    {
        return -1;
    }
    
    for (int idx = total_num - 1; idx > originIdx; --idx)
    {
        if (numbers[idx] > numbers[originIdx])
        {
            answer = numbers[idx];
        }
    }
    
    return answer;
}

vector<int> solution(vector<int> numbers) {
    int tot_cnt = numbers.size();
    stack<int> stack;
    vector<int> answer;
    
    answer.resize(tot_cnt);
    
    for (int i = 0; i < tot_cnt; ++i) 
        answer[i] = - 1;
    
    // stack 을 하나 두기
    // vector 에 새로운 값을 접근할 때마다  stack 에 있는 값을 꺼내면서 
    // 만약 현재 값보다 작으면, 해당 값으로 세팅해주기
    // 그리고 현재 접근한 대상의 idx 를 추가
    
    for (int idx = 0; idx < tot_cnt; ++idx)
    {
        int cur_num = numbers[idx];
        
        while(stack.empty() == false)
        {
            int stack_idx = stack.top();
            int stack_num = numbers[stack_idx];
            
            if (stack_num >= cur_num)
            {
                break;
            }
            
            stack.pop();
            answer[stack_idx] = cur_num;
        }
        
        stack.push(idx);
    }
    
    return answer;
}