Programers 주식가격

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

프로그래머스

프로그래머스 주식가격 문제입니다.

 

아이디어

주식가격을 가격이 아닌 순서를 기반으로 stack을 이용하여 풀어냈습니다.

현재 가격이 다음가격보다 크지 않다면 stack에서 꺼내고 떨어지지 않은 가격의 sec를 저장했습니다.

아래 코드의 주석을 통해 어렵지 않게 이해할 수 있습니다.

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
vector<int> solution(vector<int> prices) {
    int size = prices.size();
    vector<int> answer(size);
    stack<int> st;
    //position기반으로 처리
    for (int i = 0; i < size; i++) {
        //stack이 비었거나 가격이 떨어졌을때
        while (!st.empty() && prices[st.top()] > prices[i]) {
            //해당 position에 대한 처리
            answer[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    while (!st.empty()) {
        answer[st.top()] = size - st.top() - 1;
        st.pop();
    }
    return answer;
}