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

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

Solution

1. 이중 for문

#include <vector>

using namespace std;

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

막상 풀고나서 생각해보니 어디서 상당히 많이 본 문제였다. 어디라고 말은 할 수 없으나 시험문제로 나왔던 기억이 난다.

1초 시점에서는 단 한번도 떨어진 적이 없다. 그렇지만 3초 시점에서는 바로 다음 시점에서 떨어진다. 4초는 마지막 시점까지 떨어지지 않는다. 5초 시점에는 어차피 본인말고 없으니 계산을 할 수 없다.

간단하다. 현재 시점에서 계속 다음 시점을 체크하며 가격이 떨어졌다면 break 처리한 후 얼마나 오래 갔는지 카운트하면 그만이다.

근데 이렇게 간단하게 풀릴 것 같으면 왜 이제 레벨2인지 의심스러웠다.

2. 스택 사용

절대 그렇게 간단히 풀릴 문제가 아니다. (아마 그땐 저딴식으로 풀어서 떨어지지 않았을까? 어떤 곳인지 밝힐 수는 없다. 사실 기억도 잘 안남...)

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

vector<int> solution(vector<int> prices) {
    int N = prices.size();
    vector<int> answer(N);
    stack<int> stk;
    for (int i = 0; i < N; i++) {
        while (!stk.empty() && prices[stk.top()] > prices[i]) {
            answer[stk.top()] = i - stk.top();
            stk.pop();
        }
        stk.push(i);
    }
    while (!stk.empty()) {
        answer[stk.top()] = N - stk.top() - 1;
        stk.pop();
    }
    return answer;
}

스택을 활용하는 이유는 시점의 순서대로 데이터를 갱신하기 위해서. 얼마나 오래 떨어지지 않았는가를 확인하기 위해서다.

for (int i = 0; i < N; i++) {
    while (!stk.empty() && prices[stk.top()] > prices[i]) {
        answer[stk.top()] = i - stk.top();
        stk.pop();
    }
    stk.push(i);
}
while (!stk.empty()) {
    answer[stk.top()] = N - stk.top() - 1;
    stk.pop();
}
return answer;

우선 스택에 시점(인덱스)를 순서대로 쌓되, 해당 시점에 이전에 쌓아뒀던 스택의 top에있는 데이터랑 비교했을 때(첫 pop이 시행된다는 기준에서 바로 직전에 떨어진 시점) 만약 현재 시점에 값이 떨어졌다면, top 시점에 i 시점부터 top 까지 시간 텀을 해당 시점 answer 벡터에 갱신하고 해당 값은 pop 한다.

각 데이터마다 시점으로 따지면 이중 for문을 돌려도 된다. 그렇지만 전체 시점으로 생각을 해 보자.

1,2,3,2,3 은 총 5개(0,1,2,3,4) 의 시점을 가지고 있다. 2번 시점에서는 3번 시점에서 가격이 바로 떨어졌기에 1이 갱신될것이다. 나머지 데이터들 또한 이 시점을 기준으로 생각했을 때 각각 4, 3, 1, 1, 0이라는 결과가 나온다.

전체 시점을 한번 살펴본 후 스택에 남아있는 데이터들을 마저 처리해준다. 각 top은 전체 시간 N - 본인의 시점 - 1 시점이 떨어진 시점이므로 각 시점 데이터에 갱신해준다.

이중 for문은 각 시점을 다 독립적으로 처리한다. 스택은 그렇지 않고 조금 더 고급지게 처리하는 차이가 있다. 사실 이 문제에서 조건 내에서는 두 방법 다 정답 처리가 된다만...데이터의 크기가 매우 커진다면 후자가 훨씬 나은 선택이지 않을까.