Programmers / Stack, Queue / 주식가격

< 문제링크 >

https://www.welcomekakao.com/learn/courses/30/lessons/42584

< 풀이 >

1. 자신보다 작은 값이 나올 때 까지 계속해서 stack에 push

2. 작은 값이 나왔을 때, 그 값보다 큰 값들은 시간을 계산하고 전부 pop

3. 마지막 항목까지 했을 때, 스택에 남은 항목들에 대한 처리가 필요하다.

< 코드 >

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    // 제일 처음 항목은 stack에 넣기
    s.push(0);
    int size = prices.size();
    for (int i = 1; i < size; i++) {
        // 가격이 떨어지는 시점
        if (prices[s.top()] > prices[i]) {
            // 현재 가격보다 높은 가격들은 시간계산 후 pop
            while (!s.empty() && prices[s.top()] > prices[i]) {
                int idx = s.top();
                answer[idx] = i - idx;
                s.pop();
            }
        }
        s.push(i);
    }
    // 스택에 남은 항목들 처리
    while (!s.empty()) {
        int idx = s.top();
        answer[idx] = size - 1 - idx;
        s.pop();
    }

    return answer;
}