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

• 출처: 프로그래머스 42584
• 분류: 스택/큐 · Lv.2

문제

초 단위로 기록된 주식가격 배열 prices가 주어진다. 각 시점의 가격이 떨어지지 않은 기간(초)을 배열로 반환하라.

핵심

단조 스택(monotone stack)으로 아직 가격이 떨어지지 않은 시점들을 관리한다. 현재 가격이 스택 top보다 낮으면 그 시점의 답이 확정된다.

풀이

#include <stack>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    int n = prices.size();
    vector<int> answer(n);
    stack<int> st;

    for (int i = 0; i < n; i++) {
        while (!st.empty() && prices[st.top()] > prices[i]) {
            answer[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }

    while (!st.empty()) {
        answer[st.top()] = n - 1 - st.top();
        st.pop();
    }

    return answer;
}

메모

• 스택에 가격이 아닌 인덱스를 저장한다. 답을 계산할 때 i - st.top()으로 경과 시간을 바로 구할 수 있다.
• prices[st.top()] > prices[i]: 가격이 떨어진 순간이다. 해당 시점의 답은 i - st.top()으로 확정된다.
• 루프가 끝난 뒤 스택에 남은 인덱스들은 끝까지 가격이 떨어지지 않은 시점이다. n - 1 - st.top()이 답이 된다.
• 브루트포스(이중 루프)도 O(N²)으로 통과 가능하지만, 스택 풀이가 O(N)으로 더 효율적이다.

복잡도

풀이	시간	공간
스택	O(N)	O(N)
이중 루프	O(N²)	O(N)

N = prices 길이. 스택 풀이에서 각 인덱스는 최대 한 번 push, 한 번 pop된다.