주식가격

문제

일단 문제를 풀지 못하였다.
그 이유는 문제를 잘못 이해하였다.

prices에서 특정한 인덱스 x를 기준으로 x보다 인덱스가 작은 원소들은 생각하지 않고 인덱스가 큰 원소들만을 볼 때, 그 중 인덱스 x의 값보다 크거나 같은 원소가 몇개인가를 찾는 문제로 착각을 했다.

그런데 문제는 그게아니었다.
문제는 똑같이 x를 기준으로 할 때 자신보다 큰 인덱스 중에서 나보다 값이 낮은 경우는 언제 발생하냐가 문제였다.

전자의 경우로 생각을 하다보니까 n의 개수를 10만개로 잡은 문제이기 때문에
$O(nlogN)$ 이하의 알고리즘을 찾아야 겠다고 생각을 하고 찾다보니 결국엔 답을 찾지 못하였다.

그래서 이번거는 프로그래머스에서 가장 인기 있는 답안을 하나 가져와서 설명을 하겠다..

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

using namespace std;

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

2중 for문을 통한 풀이는 시간복잡도 $O(n^2)$이 나오게 된다.
하지만 이렇게 스택을 이용하게 되면 시간복잡도 $O(n)$이 나온다.

먼저 여기서 n은 prices의 길이이다. 이 점을 착안해서 보았을 때

위의 코드에서는 for문 내부의 있는 while문은 n과는 연관이 없다고 볼 수 있다. (n보다는 무조건 작을 것임)

그래서 stack의 pop과 top 연산의 경우 $O(1)$의 시간복잡도를 가지고 있기 때문에 시간복잡도는 $O(n)$으로 볼 수 있다.