[프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 주식가격

스택 문제

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

 

---

[문제 풀이]

 

주식의 가격이 떨어지지 않는 기간을 구하는 문제입니다.

 

단순하게 생각한다면 이중 for문을 사용하여서 현재 가격이 유지되는 시간을 구하면 풀이가 가능합니다.

그러나 위의 풀이는 $O(N^2)$의 시간 복잡도를 갖고 배열의 크기 N의 최대가 100,000이므로 효율이 매우 떨어집니다.

$O(N^2)$의 풀이가 통과가 되는 것 같지만 실제로는 그렇게 풀면 안 됩니다.

 

주어진 순서대로 특정 상태가 유지되는지 확인하는 문제이므로 스택의 느낌이 납니다.

예시로 어떻게 푸는지 흐름을 보여드리면 스택으로 풀이할 방법이 보일 겁니다.

 

 

prices가 [1, 2, 3, 2, 0, 1]처럼 주어져 있다고 가정하겠습니다.

 

우선 1초 시점의 1원, 2초 시점의 2원, 3초 시점의 3원까지는 가격이 떨어지지 않는 양상을 유지합니다.

 

그러나 4초 시점의 2원이 등장하면서 3초 시점의 3원은 가격이 떨어지게 되었습니다.

그러므로 3초 시점에서는 4 - 3 = 1초만큼 가격이 유지되었음을 알 수 있습니다.

 

그리고 5초 시점의 0원이 등장하면서 1, 2, 4초 시점 역시 가격이 떨어지게 되었습니다.

그러므로 1초 시점에서는 5 - 1 = 4초만큼, 2초 시점에서는 5 - 2 = 3초만큼, 4초 시점에서는 5 - 4 = 1초만큼 유지되었습니다.

 

마지막으로 6초 시점에서는 1원이 들어왔으므로 남은 5초와 6초 시점은 가격이 떨어지지 않는 양상입니다.

하지만 6초가 마지막 시간이었으므로 5초 시점에서는 6 - 5 = 1초만큼, 6초 시점에서는 6 - 6 = 1초만큼 유지됩니다.

 

 

위의 예시에서 가격이 떨어지지 않는 양상이 보이면 계속 다음 주가를 확인하다가,

가격이 떨어지게 되면 밑줄 친 부분처럼 (현재 시간) - (주식이 등장한 시간)으로 가격이 떨어지지 않은 시간을 알 수 있었습니다.

 

여기서 가격이 떨어지지 않는 양상이 보이면 계속 다음 주가를 확인한다는 것은

아직 가격이 떨어지지 않은 상태의 주식들이 비내림차순으로 정렬되어있음을 의미합니다.

위의 예시에서 3초까지는 1원, 2원, 3원의 형태처럼 비내림차순으로 정렬된 것을 확인할 수 있습니다.

 

주식들이 비내림차순으로 정렬된 상태를 계속 유지하는 것이 매우 중요합니다.

왜냐하면 이 성질로 인해 이 문제를 스택으로 $O(N)$에 풀 수 있기 때문입니다.

 

주식들이 비내림차순으로 존재한다는 것은, 가격이 떨어지는 상황에서 이전까지의 모든 주식을 확인할 필요 없이 가장 최근에 들어온 주식 (가장 주가가 높은 주식)부터 확인해도 문제가 없게 합니다.

그리고 최근에 들어온 원소부터 $O(1)$에 확인할 수 있는 스택이 이 문제에서 시간 복잡도를 단축시키게 하는 핵심 자료구조가 되는 것입니다.

 

위의 예시에서 볼 수 있듯이 3초까지 들어온 주가는 1원, 2원, 3원 순서대로 비내림차순이었습니다.

그리고 4초에 들어온 주식인 2원에 의해 가격이 떨어지는 상황인지 확인하기 위해 아래와 같은 과정을 거치게 됩니다.

 

1. 가장 마지막에 들어온 (가장 주가가 높은) 3초의 3원이 가격이 떨어진 것을 확인하고, 
2. 그전에 들어온 2초의 2원은 가격이 떨어지지 않았으므로 확인을 마침.
3. 1초는 당연히 2원보다 작거나 같으므로 확인할 필요가 없음.

이중 for문을 사용하여 $O(N^2)$에 이 문제를 해결한다는 것은 아직 가격이 떨어지지 않은 주식들이 비내림차순으로 정렬되어 있다는 특징을 활용하지 않은 풀이입니다.

4초에 2원의 주식이 들어왔을 때, 3초와 2초만 확인하지 않고 굳이 1~3초의 모든 주가를 확인하게 되는 것입니다.

테스트 케이스의 크기가 작으니 큰 차이가 없어 보이지만 N이 100,000이라면 그 차이는 매우 커지게 됩니다.

 

 

이제 주식들을 스택으로 관리한다는 사실을 알았으니 answer에 가격이 떨어지지 않은 상태가 몇 초였는지만 기록하면 문제를 해결할 수 있습니다.

 

현재 주가로 인해 가격이 떨어지는지 가장 최근에 등장한 주식 (가장 주가가 높은 주식)을 확인합니다.

이 과정에서 가장 최근에 등장한 주식을 확인하기 위해 스택을 사용합니다.

 

가격이 떨어지지 않는다면 계속 스택에 주식에 대한 정보를 넣습니다.

가격이 떨어지게 되었다면 가격이 떨어진 모든 주식에 대해 주식이 등장한 시간 k초를 미리 스택에 저장해두어 answer[k]에 주가가 떨어지지 않고 지속된 시간인 (현재 시간) - k을 기록합니다.

 

마지막으로 모든 반복문을 마친 후에 스택에 남아 있는 주식들은 처음부터 끝까지 주가가 떨어지지 않고 지속된 것이므로 answer[k]에 (전체 시간) - k를 기록합니다.

 

 

요약하자면

 

• 스택으로 주식이 몇 초에 등장했는지 저장
• 스택의 top이 현재 주식에 의해 가격이 떨어지게 되었다면 (현재 시간) - (주식이 등장한 시간)을 answer에 기록. 가격이 떨어지지 않게 될 때까지 스택을 pop 하며 반복.
• 마지막에 스택에 남은 원소들은 끝까지 가격이 떨어지지 않았음을 의미하므로 (전체 시간) - (주식이 등장한 시간)을 answer에 기록

의 과정으로 해당 문제를 $O(N)$에 해결할 수 있습니다.

---

 

[소스 코드] / C++

 

저는 클래스로 주가와 시간을 묶었지만 시간을 기록한다면 prices배열을 사용하여 주가를 확인할 수 있으므로 클래스를 만들지 않아도 풀이가 가능합니다.

 

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

using namespace std;

class Stock {
public:
    int t, p;
    
    Stock (int t, int p) {
        this->t = t;
        this->p = p;
    }
    
    ~Stock() {}
};

vector<int> solution(vector<int> prices) {
    int N = prices.size();
    
    vector<int> answer(N);
    stack<Stock> st;
    
    for (int i = 1; i < N + 1; i++) {
        int price = prices[i - 1];
        
        while (!st.empty()) {
            Stock pre = st.top();
            int p = pre.p, t = pre.t;
                
            if (price >= p) break;
            
            answer[t - 1] = i - t;
            st.pop();
        }
        
        st.push(Stock(i, price));
    }
    
    while (!st.empty()) {
        Stock pre = st.top();
        int p = pre.p, t = pre.t;
        st.pop();
        
        answer[t - 1] = N - t;
    }
    
    return answer;
}