[프로그래머스] 주식 가격

문제 접근

무난한 stack문제
stack에는 최신에 나온 값보다 작은 가격들만 들어있음!
만약 stack의 top이 현재 나온 숫자보다 크다면, pop()해주고, 현제 index와 비교하여, 저장한다.

pair를 만들 필요없이, 그냥 index만 stack에서 넣어서 했으면, 더 깔끔했을 거 같다.

코드 구현(c++)

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<pair<int, int> > s;
    for(int i = 0 ; i < prices.size() ; i++){
        if(!s.empty()){
            while(!s.empty() && s.top().first > prices[i]){ // stack에 존재하는 탑 값이 가장 큰값이고, 해당 값이 다음 초에 있는 것보다 작다면, pop()해주고 answer에 넣어주기
                answer[s.top().second] = i - s.top().second;
                s.pop();
            }
        }
        s.push(make_pair(prices[i], i));
    }
    while(!s.empty()){
        answer[s.top().second] = prices.size() - 1 - s.top().second;
        s.pop();
    }
    return answer;
}