프로그래머스 - 주식가격

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

 

문제 설명

초 단위로 기록된 주식 가격이 있다.
각 시간마다 가격이 떨어지지 않은 초를 구하자.

 

제한 사항

• 1 <= 가격 <= 10,000
• 2 <= 시간 <= 100,000

 

1. 반복문 - O(N^2) - 시간초과(인 경우가 있음)

 

우선 예제를 보면서 답을 어떻게 도출하는지 알아보자.

 

[1,2,3,2,3]

---

1초 시점의 가격은 1이다.
이 가격은 2초 시점의 가격보다 낮다. 따라서 가격이 떨어지지 않았다.
이 가격은 3초 시점의 가격보다 낮다. 따라서 가격이 떨어지지 않았다.
이 가격은 4초 시점의 가격보다 낮다. 따라서 가격이 떨어지지 않았다.
이 가격은 5초 시점의 가격보다 낮다. 따라서 가격이 떨어지지 않았다.
1초 시점의 가격은 마지막인 5초 시점까지 떨어지지 않았다.
따라서 4초 동안 가격이 떨어지지 않았다.

2초 시점의 가격은 2다.
이 가격은 3초 시점의 가격보다 낮다. 따라서 가격이 떨어지지 않았다.
이 가격은 4초 시점의 가격보다 낮다. 따라서 가격이 떨어지지 않았다.
이 가격은 5초 시점의 가격보다 낮다. 따라서 가격이 떨어지지 않았다.
2초 시점의 가격은 마지막인 5초 시점까지 떨어지지 않았다.
따라서 3초 동안 가격이 떨어지지 않았다.

3초 시점의 가격은 3이다.
이 가격은 4초 시점의 가격보다 높다.
즉,4초 시점에서 가격이 떨어졌다.
따라서, 3초에서 1초 뒤 가격이 떨어졌으므로, 1초간 가격이 떨어지지 않았다.

4초 시점의 가격은 2다.
이 가격은 5초 시점의 가격보다 낮다. 따라서 가격이 떨어지지 않았다.
4초 시점의 가격은 마지막인 5초 시점까지 떨어지지 않았다.
따라서 1초 동안 가격이 떨어지지 않았다.

5초 시점은 끝이다. 5초에서 시작해 5초에서 끝나면 결국 시간 차이는 0이다.

---

 

위의 과정은 반복문을 이용하여 표현할 수 있어 보인다.
i초 째의 가격을 기억한 후, i+1초부터 차례대로 순회한다. 그리고 i초 째의 가격보다 낮은 가격인 j초를 발견했다면, i초 째의 답에 j-i초를 기록하면 된다.
만약 끝까지 가격이 떨어지지 않았다면, 마지막 초 - i초를 기록하면 된다.

그럼 코드로 표현해보자.

 

solution_loop.cpp

#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    
    for (int i=0; i<static_cast<int>(prices.size())-1; ++i)
    {
        for (int j=i+1; j<static_cast<int>(prices.size()); ++j)
        {
            if (prices[i] > prices[j])
            {
                answer[i] = j-i;
                break;
            }
        }
        if (0 == answer[i])
            answer[i] = static_cast<int>(prices.size()) - i - 1;
    }
    
    return answer;
}

 

프로그래머스 테스트케이스 상으로는 시간초과가 발생하지 않는다. 위의 코드로도 효율성 테스트도 통과가 가능하다.
하지만 다음과 같은 테스트 케이스가 들어온다면, 시간 초과가 발생할 것이다.

[1,1,1,1,1,1,...,1,1,1]	// 1이 100,000개 들어있는 배열

 

2. 스택 - O(N)

 

그러면 효율적으로 답을 구할 수 있는 방법을 찾아야 한다.

다시 한번 예제를 살펴보자.

 

[1,2,3,2,3]

 

1초때의 가격은 1이다.
2초때의 가격은 2다.

만약 2초 때의 가격이 3초 때에도 떨어지지 않았다면, 1초 때의 가격도 떨어지지 않았을 것이다.
1초 때의 가격은 2초 때의 가격보다 작고,
2초 때의 가격이 3초 때에도 떨어지지 않았다면,
3초 때의 가격은 2초 때의 가격보다 크거나 같음을 의미한다.
따라서 1초 때의 가격은 자동적으로 떨어지지 않았음을 알 수 있다.

그러면 1초 때의 가격보다 떨어졌는지의 여부를 언제 확인하면 될까?
2초 때의 가격보다 떨어진 때가 왔을 때 확인하면 된다.
이 때는 1초 때의 가격보다 큰지, 작은지, 같은지 알 수 없다. 비교롤 해 봐야 한다.

따라서, 가격이 계속 떨어지지 않고 있다면 차근차근 그 가격을 스택에 쌓아두자. 그러면 스택의 top은 계속해서 크기가 유지되거나 커질 것이다.

큰 가격은 나중에 들어온다. 그리고 확인하면 먼저 기록하고 스택에서 빠져나가야 한다.
따라서 이번 문제에서는 스택을 사용하여 풀면 효율적으로 풀 수 있다.

 

만약 프로그래머스 문제를 차근차근 풀고 있었다면, 익숙한 문제일 것이다.
이 문제와 프로그래머스 - 탑 문제는 상당히 유사한 문제이다.

탑 문제를 스택을 써서 풀었다면,
이번 문제도 약간의 변형만으로 풀 수 있다.
순회 방향과 크기 비교, 그리고 마지막에 끝까지 값이 떨어지지 않은 항목에 대해 신경을 써 줘야 하는 점이 추가됐다.

탑 문제에서는 위치 저장을 위해 또 다른 스택을 사용했었으니, 이번에는 하나의 스택에 pair 자료구조를 이용하여 한 데 묶어서 저장해보자.

 

solution_stack.cpp

#include <vector>
#include <stack>
#include <utility>

using namespace std;
using PR = pair<int, int>;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    stack<PR> st;
    
    for (int i=0;i<static_cast<int>(prices.size());++i)
    {
        while(!st.empty())
        {
            PR info = st.top();
            if (prices[i] < info.first)
            {
                answer[info.second] = i - info.second;
                st.pop();
            }
            else
                break;
        }
        st.push({prices[i],i});
    }
    
    while (!st.empty())
    {
        PR info = st.top();
        answer[info.second] = static_cast<int>(prices.size()) - info.second - 1;
        st.pop();
    }
    
    return answer;
}

 

문제를 풀다 보면 전에 풀었던 문제와 유사한 문제가 나올 수 있다. 그 문제를 제대로 이해하고 풀었다면, 유사한 문제는 손쉽게 풀 수 있을 것이다.

물론 예외가 있을 순 있다.