[Programmers] Lv2. 주식가격 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

문제 지문의 설명이 너무 전달력 없이 작성되어 있어, 다른 분이 재해석하신 글을 참고하였습니다. 저는 스택(Stack)을 이용하여 풀었습니다.

• prices의 크기만큼 answer 배열에 메모리 공간을 할당해둔다.
• 스택에 저장되는 데이터는 <주가 금액, 스택에 진입한 시점의 시각(초)>이다.
• for문을 통해, 1초부터 prices 크기까지 초를 세며 진행한다.
  • 스택이 비었거나, 현재 주가가 스택 top()의 주가보다 크다면 현재 주가와 시간을 스택에 삽입한다.
  • 위 조건에 해당하지 않는다면, 주가가 낮아진 것이므로 스택에서 현재 주가보다 큰 주가들을 pop한다.
    • pop한 주가의 가격 유지 시간은 (prices 크기 - pop한 주가의 스택 진입 시점)이다.
    • pop한 주가의 스택 진입 시점(초)에서 1을 빼면, 해당 주가의 원래 인덱스이므로 answer 배열의 해당 인덱스 자리에 pop한 주가의 가격 유지 시간을 저장한다.
  • 조건에 따라 pop을 다 했다면, 현재 주가와 시간을 스택에 삽입한다.
• for문을 다 돌고, 스택에 남은 주가들에 대해 위의 pop 과정들을 반복한다.

 

✏️소스 코드 및 결과

#include <vector>
#include <stack>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    stack<pair<int, int>> priceStack;    // <주가, 스택 진입 시각>
    
    for (int second = 1; second <= prices.size(); second++) {
        int index = second - 1;

        if (priceStack.empty() or priceStack.top().first < prices[index]) {
            priceStack.emplace(prices[index], second);
            continue;
        }

        while (!priceStack.empty()) {
            pair<int, int> top = priceStack.top();
            
            if (top.first <= prices[index])
                break;
            
            int holdingTime = second - top.second;
            int targetIdx = top.second - 1;
            answer[targetIdx] = holdingTime;
            priceStack.pop();
        }

        priceStack.emplace(prices[index], second);
    }

    while (!priceStack.empty()) {
        int holdingTime = prices.size() - priceStack.top().second;
        int targetIdx = priceStack.top().second - 1;
        answer[targetIdx] = holdingTime;
        priceStack.pop();
    }
    
    return answer;
}