Level 2. 주식가격

Level 2. 주식가격

 

 

가장 간단한 방식이지만 효율은 좋지 않다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices)
{
    size_t n = prices.size();
    vector<int> answer(n, 0);

    for (int i = 0; i < n; ++i)
        for (int j = i; (j < n - 1) && (prices[i] <=prices[j]); ++j)
            ++answer[i];

    return answer;
}

 

인접한 두 가격 사이에 감소하는 지점을 찾은 후, 해당 감소 지점보다 낮은 이전 가격을 찾아가는 방식이다.

 

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

    for (int i = 0; i < size; ++i)
    {
        while (!stck.empty() && prices[i] < prices[stck.top()])
        {
            answer[stck.top()] = i - stck.top();
            stck.pop();
        }

        stck.emplace(i);
    }

    while (!stck.empty())
    {
        answer[stck.top()] = size - stck.top() - 1;
        stck.pop();
    }

    return answer;
}