프로그래머스 - 주식 가격 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=cpp#

프로그래머스

 

큐, 스택을 사용하는 문제는 코딩테스트에 빈출로 출제된다. 

 

이 문제의 예제를 통과시키는 것은 쉽다. O(N^2)으로 이중 반복문을 쓰면 간단하게 풀린다. 하지만 이렇게하면 N의 크기가 10만이기 때문에 시간초과가 발생할 수 있다. 다행히 이 문제에선 그렇지 않지만 스택이나 큐를 사용해서 최적화를 반드시 해줘야한다.

 

스택을 사용해 최적화할 수 있는데 언제나 스택이나 큐에 먼저 다 넣어놓고 시작했었는데 순차적으로 넣어가면서 풀이해야했다.

 

먼저 최적화해야할 부분을 생각해보면

 

1 2 3 2 3

 

1 -> 2, 3, 2, 3 까지 비교

2 -> 3, 2, 3 까지 비교

3 -> 2, 3 까지 비교

2 -> 3 까지 비교

 

해야한다. 직관적이지만 비효율적이다. 그렇다면 먼저 스택에 넣어놓고 바로 앞의 수를 계속 비교하도록 하면 어떨까? 

무슨말이냐하면

1과 2를 비교한 후 1과 3을 비교하는 것이 아니라, 2와 3을 비교시키는 것이다. 그리고 3과 2를 비교시킨다. 그리고 만약 주식이 떨어졌으면 이 때 정답을 갱신한다. 

 

1 -> 2와 비교

2 -> 3과 비교

3 -> 2와 비교 -> 값이 떨어졌으므로 이전값 2와 비교 

2 -> 3과 비교

 

이렇게하면 1은 모두와 비교하지 않게되고 효과적으로 비교 횟수가 줄어들었음을 알 수 있다. 그리고 3->2 비교 구간에서ㅓ 값이 떨어졌으므로 이전값과 비교하는 부분에서 스택의 성질을 활용할 수 있다.

 

1. 스택이 비어있거나 현재 스택의 탑 값(바로 이전 값) 과 지금 값을 비교했을 때 값이 떨어졌다면

2. answer를 갱신한다.

3. 스택에서 값을 뺀다. 즉 3번에서 3과 2를 비교중인데 3을 뺀다. 그럼 2와 2를 비교하게 된다.

 

이 과정을 반복하면 중간에 주식이 떨어진 값들은 스택에서 이미 나와있을 것이고, 중간에 떨이지지 않고 계속 증가하거나 유지한 주식은 남아있을 것이다.

 

문제를 파악할 때 어떻게든 스택과 큐의 성질을 끼워맞추려하지 말고 먼저 어떻게 최적화할 수 있을까를 고민해야할 것 같다.

 

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

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    
    stack<int> st;
    
    for(int i = 0; i < prices.size(); 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()] = prices.size() - st.top() - 1;
        st.pop();
    }
    
    return answer;
}