[2023년 11월 23일]주식가격(16분)

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

구현 아이디어 7분 구현 9분

풀이

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

// stack에 인덱스 넣으며 진행.
// stack의 top의 인덱스에 있는 prices가 현재 넣을 prices의 인덱스보다 클 때 처리.

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    
    stack<int> indices;
    
    for(int i = 0; i < prices.size(); ++i)
    {
        int cur_price = prices[i];
        if(indices.empty()) indices.push(i);
        else
        {
            while(!indices.empty())
            {
                if(cur_price < prices[indices.top()])
                {
                    answer[indices.top()] = i - indices.top();
                    indices.pop();
                }
                else break;
            }
        }
        indices.push(i);
    }
    
    while(!indices.empty())
    {
        int index = indices.top();
        answer[index] = prices.size() - 1 - index;
        indices.pop();
    }
    
    return answer;
}