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

스택을 이용하는 문제이다. 스택에 전 시간들을 기록해놓으면, 현재 시간의 가격과 스택에 쌓인 시간들의 가격을 비교해서 정답을 유추할 수 있다.

 

과정을 나눠보면 다음과 같다.

1. 지간 값을 담을 스택 s를 만든다. 그리고 정답을 담을 벡터 v를 만든다.

2. 시간을 1초부터 입력받은 가격 크기(총 시간에 해당)초 만큼 루프를 돌면서,

3. s에 현재 시간값을 넣어준다.

4. 만약 s가 비어 있지 않고 s의 top에 있던 시간 (바로 이전 시간)의 가격이 현재 시간 가격보다 큰 경우,

5. (현재 시간 - top에 있던 시간)값을 v[top에 있던 시간]에 기록하고 s를 pop한다. 이 값은 가격이 떨어지는 기간이다.

6. 5번 작업을 3번 조건이 만족하지 않을때까지 반복한다. (이전 시간들의 가격이 현재 시간 가격보다 작은 경우에는 정답을 도출해낼 수 있기 때문이다.)

7. 위 과정을 거친 후, 아직 스택에 남은 시간들은 정답을 계산해준다. (이 시간값은 끝까지 가격이 떨어지지 않은 경우이다.)

위의 예 [1, 2, 3, 2, 3] 예를 들어보자.

우선 스택 s와 벡터 v를 만든다.

스택 s -> { }(top)
벡터 v -> [0, 0, 0, 0, 0] (크기만큼 할당)

1초부터 시작하면

case : 1초

[ 1(1초), 2(2초), 3(3초), 2(4초), 3(5초) ]

s -> {}(top) -> push -> {1초}(top)

v -> [0, 0, 0, 0, 0]

스택이 비어 있으므로 특별한 작업없이 스택에 현재 시간을 넣는다. 

 

case : 2초

[ 1(1초), 2(2초), 3(3초), 2(4초), 3(5초) ]

s -> {1초}(top) -> push -> {1초, 2초}(top)

v -> [0, 0, 0, 0, 0]

스택이 비어있지 않으므로 top에 있는 시간 값의 가격을 가지고 온다. 현재 top의 값을 1초 이므로 1초일때 가격은 1이다. 현재 시간 가격 2보다 작으므로 정답을 구하는 조건에 성립하지 않는다. 그리고 스택에 현재 시간을 넣는다.

 

case : 3초

[ 1(1초), 2(2초), 3(3초), 2(4초), 3(5초) ]

s -> {1초, 2초}(top) -> push -> {1초, 2초, 3초}(top)

v -> [0, 0, 0, 0, 0]

위와 같다.

 

case : 4초

[ 1(1초), 2(2초), 3(3초), 2(4초), 3(5초) ]

s -> {1초, 2초, 3초}(top) -> pop(3초) -> 조건 (3(3초) > 2(4초)) 만족 -> push -> {1초, 2초, 4초}(top)

v -> v[3초] = 4초 - 3초 -> [0, 0, 1(3초), 0, 0]

4초일 경우 이전 가격보다 작아졌으므로 조건을 만족하게 된다. top의 값 3초를 스택에서 꺼낸 후 가격을 비교 한다. 3초일때 가격 3이 4초일때 가격 2보다 크므로 벡터 3번째 원소에 정답을 넣으면 된다. 정답은 (현재 시간 - top에 있던 시간) 이므로 3 - 2 = 1이 된다.

 

case : 5초

[ 1(1초), 2(2초), 3(3초), 2(4초), 3(5초) ]

s -> {1초, 2초, 4초}(top) -> push -> {1초, 2초, 4초, 5초}(top)

v -> [0, 0, 1(3초), 0, 0]

조건을 만족하지 않으므로 스택에 현재 값만 집어 넣는다.

 

모든 루프를 돌았다. 이제 스택에 남은 시간 값을 처리한다. 이 시간 값의 가격들은 끝까지 가격이 내려가지 않은 경우가 된다. 

s ->  {1초, 2초, 4초, 5초}(top) -> 차례대로 꺼내면 5초, 4초, 2초, 1초

v   -> 5초 : (총 시간) - 5초 = 0초 -> [0, 0, 1(3초), 0, 0(5초)]
    -> 4초 : (총 시간) - 4초 = 1초 -> [0, 0, 1(3초), 1(4초), 0(5초)]
    -> 2초 : (총 시간) - 2초 = 3초 -> [0, 3(2초), 1(3초), 1(4초), 0(5초)]
    -> 1초 : (총 시간) - 1초 = 4초 -> [4(1초), 3(2초), 1(3초), 1(4초), 0(5초)]

이렇게 최종 값 [4, 3, 1, 1, 0]이 나왔다.

 

코드는 다음과 같다.

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

vector<int> solution(vector<int> prices) 
{
    int n = prices.size();
    // 정답을 담을 벡터
    vector<int> answer(n);
    // 정답을 도출하기 위한 스택
    stack<int> s;
    // 1초부터 ~ 최종 시간까지 (인덱스접근이므로 0부터)
    for(int i = 0; i < n; ++i)
    {
        // 스택에 값이 있고 현재 시간 가격보다 top 시간 가격이 더 큰경우까지
        // 루프를 실행
        while(!s.empty() && prices[s.top()] > prices[i])
        {
            int time = s.top();
            s.pop();
            // 가격이 떨어진것이므로 현재 시간에서의 정답을 입력한다.
            // (현재 시간) - (top 시간)
            answer[time] = i - time;
        }
        // 현재 시간을 스택에 넣는다.
        s.push(i);
    }
    
    // 스택이 남아있는 경우
    // 끝까지 가격이 떨어지지 않은 경우
    while(!s.empty())
    {
        int time = s.top();
        s.pop();
        // (최종 시간) - (top 시간)을 해준다.
        // 인덱스 접근을 고려하여 -1을 해줘야 한다.
        answer[time] = n - 1 - time;
    }
    
    return answer;
}