프로그래머스 - 주식가격 (Lv.2)

문제 링크

• 주식가격

문제 접근

• prices 는 시간 순서대로 가격이 담겨 있다. 즉, 배열의 인덱스 는 시간이라고 볼 수 있다.
• 배열을 탐색하면서 가격이 떨어지지 않는다면 스택에 배열의 인덱스(시간)을 담는다.
• 가격이 떨어진다면, answer[stk.top()] = i - stk.top() 를 담고, 스택의 top() 에 위치한 원소를 버린다.
  • 스택에는 각 배열의 인덱스(시간)가 담겨 있으므로, 해당 위치에 가격이 떨어지지 않은 시간을 계산하여 저장한다.
  • 가격이 떨이지지 않을 때 까지 스택의 top 원소와 비교하며 위 과정을 반복한다.
• 스택에 남아 있는 원소는 끝까지 가격이 떨어지지 않았던 가격들로, 마찬가지로 배열의 최종 길이(n-1)에서 시간을 계산하여 저장한다.

구현(All Pass)

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

using namespace std;

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