[프로그래머스] 주식 가격 (C++)

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

코딩테스트 연습 - 주식가격

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    for (int i=0; i<prices.size(); i++){
        while (!s.empty() && prices[s.top()]>prices[i]){        //내려갔을 때
            answer[s.top()]=i-s.top();
            s.pop();
        }
        s.push(i);
    }
    while (!s.empty()){
        answer[s.top()]=prices.size()-s.top()-1;
        s.pop();
    }
    return answer;
}

 

O(N^2) 로만 푸는 방법밖에 생각이 안나서 구글링..

 

stack을 이용하면 된다.

스택을 차례대로 쭉 쌓아주면서, stack의 top 인덱스 prices 값과, 현재 넣으려는 prices 값을 비교해서 현재 넣으려는 값이 top보다 작으면, 줄어든 것이므로 answer 을 갱신해준다. 이 과정을 stack 이 비지 않고, prices[s.top()]>prices[i] 일때까지 반복한다. 

 

가격이 떨어지지 않는 경우는 스택에 그대로 쭉 남아있을 것이므로, s.top() 을 이용해 값을 구해주고 pop을 해준다.

스택이 빌 때까지 반복한다.