C++ / 프로그래머스 / 주식가격

문제

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

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

문제풀이

 

스택을 이용하여 풀었다.

stack <pair <int, int>>를 이용하여 first에는 주식가격을, second에는 인덱스 값을 입력한다.

 

스택에는 현재 탐색하고 있는 주식가격 이하인 가격들만 들어있어야 한다.

따라서 탐색하고 있는 주식가격 보다 큰 가격들이 있으면 반복문을 통해 모두 pop을 한다.

pop을 하면서 인덱스 차이를 answer [기존 주식가격 인덱스]에 값을 입력한다.

 

while문이 종료되면 현재 주식가격과 인덱스를 스택에 push 한다.

 

주식가격이 담긴 배열을 다 탐색했는데도 스택에 값이 남아있다면 배열의 사이즈- 1 - 해당 주식 인덱스 값을 answer [해당 주식 인덱스]에 입력한다.

 

 

 

코드

#include <string>
#include <vector>
#include <stack>
#define pii pair<int, int>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<pii> stk;

    stk.push({ prices[0], 0 });
    for (int idx = 1; idx < prices.size(); ++idx) {
        while (!stk.empty() && stk.top().first > prices[idx]) {
            answer[stk.top().second] = idx - stk.top().second;
            stk.pop();
        }
        stk.push({ prices[idx], idx });
    }
    while (!stk.empty()) {
        answer[stk.top().second] = prices.size() - 1 - stk.top().second;
        stk.pop();
    }

    return answer;
}