[C++] Programmers Lv. 2 "주식가격"

🔵 문제 링크

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

프로그래머스

 

💡 Point

• 입력이 10만이라 O(N^2) 알고리즘은 사용할 수 없다.

 

🔷 입력이 10만이라 O(N^2) 알고리즘은 사용할 수 없다.

문제 조건을 보면 입력이 10만이다. 그렇다 함은 O(N^2) 알고리즘을 사용할 수 없는 것이다. 

어떻게 하면 더 나은 시간복잡도로 문제를 해결할 수 있을까?

 

🔷 가장 근접한 큰/작은 수

스택을 활용하면 배열의 특정 원소보다 가장 근접한 큰/작은 수를 쉽게 구할 수 있다.

이러한 기법을 모노토닉 스택이라고 한다.

 

🔷 모노토닉 스택

모노토닉 스택은 배열을 순회하면서 특정 조건(최댓값, 최솟값, 다음/이전 큰 값 등)을 만족하는 인덱스나 값을 효율적으로 찾기 위해 사용하는 스택 기법이다. 각 요소가 스택에 최대 한 번 push, 한 번 pop되므로 시간 복잡도는 O(N)이다.

 

🔷 모노토닉 스택을 이용한 풀이

우리가 지금 구하고자 하는 것은 어떤 시점의 가격이 본래 가격보다 떨어지지 않은 기간이다.

즉, 어떤 시점의 가격보다 가장 근접한 낮은 가격을 구하고, 그 가격까지의 시간 차이(여기에서는 인덱스)를 구한다.

스택을 이용하여 가격이 떨어지는 시점을 만나면, 그동안 쌓아둔 스택(이전 시점들)과 비교해 각 원소들이 가격이 떨어지지 않은 시간을 한꺼번에 계산할 수 있다.

 

예시로 1, 7, 9, 5, 6이 들어왔다고 가정하자.

 

1. i = 0, price = 1

• 스택이 비어 있음 -> push(0) (인덱스를 이용해 기간을 구함.)
• stack [0]

 

2. i = 1, price = 7

• prices[stack.top()] (스택 최상단에 있는 인덱스의 가격과 다음 가격을 비교함)
• 스택 최상단은 1이고, 다음 가격은 7이므로 stack에 7을 push.
• stack [0, 1]

 

3. i = 2, price = 9

• 2번과 마찬가지이다.
• stack[0, 1, 2]

 

4. i = 3, price = 5

• 마찬가지로 스택 최상단에 있는 인덱스의 가격인 9과 5를 비교함.
• 9에서 5로 가격 하락을 감지하면, 스택 최상단 인덱스와 현재 인덱스를 이용해 답을 구한다.
• 답을 구한 후, 스택을 pop 하여 다시 스택 최상단 인덱스의 가격인 7과 5를 비교한다.
• 가격 하락 감지했으므로, 답을 구하고 스택을 pop.
• 다시 스택 최상단 인덱스의 가격인 1과 5를 비교하는데, 이때 가격 하락이 감지되지 않았으므로 stack에 i 값을 push한다.
• stack [0, 3]

 

5. 마지막으로 i = 4, price =6

• 가격 하락 감지가 되지 않았으므로 stack에 i 값을 push한다.
• 현재 스택에는 0, 3, 4만 들어 있다.
• stack [0, 3, 4]

 

6. 마무리

• 배열을 다 순회하였을 때, 스택이 비어 있지 않다면?
• 스택에는 가격 하락이 감지되지 않은 인덱스들만 들어 있을 것이다. (0, 3, 4)
• 즉, 그 인덱스들은 가격이 내려간 적이 없으므로 총 기간에서 해당 인덱스를 빼주면 된다.

 

🔵 코드

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

using namespace std;

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

    for (int i = 0; i < prices.size(); i++)
    {
        // 1 [7 9] '5' 6

        while (!s.empty() && prices[s.top()] > prices[i])
        {
            answer[s.top()] = i - s.top();
            s.pop();
        }   
        s.push(i);
    }

    // 1 5 6
    while (!s.empty())
    {
        answer[s.top()] = prices.size() - s.top() - 1;
        s.pop();
    }

    return answer;
}

 

🔵 시간 복잡도

for문에서 입력의 길이만큼 반복하는데, 이 입력의 길이를 N이라 할 때 시간 복잡도는 O(N)이다.