[주식 가격/LV2/Python3, C++]

주식 가격 LV2

 

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

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


입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

 

 

알고리즘 고득점 Kit의 스택/큐 문제 중 하나이다.

 

스택을 사용하여 풀이하였다.

 

이후에 index에 따라 가격이 떨어지지 않은 기간을 정렬하기 위해, index와 time을 같이 담았다.

스택의 마지막 값과 비교하여 결정하였다.

 

스택에 원소가 남아있다면, 한 번도 감소하지 않았다는 의미이다.

 

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> prices)
{
    vector<int> answer;
    vector<pair<int, int>> index_time;
    vector<pair<int, int>> stk;
    
    int time = 0;
    for (int i=0; i<prices.size(); ++i)
    {
        while(!stk.empty() && prices[stk.back().second] > prices[i])
        {
            index_time.push_back(make_pair(stk.back().second, time - stk.back().first));
            stk.pop_back();
        }
        stk.push_back(make_pair(time++, i));
    }
    
    while(!stk.empty())
    {
        index_time.push_back(make_pair(stk.back().second, time-1-stk.back().first));
        stk.pop_back();   
    }

    sort(index_time.begin(), index_time.end());
    for (auto pr : index_time)
        answer.push_back(pr.second);
    return answer;
}

 

 

def solution(prices):
    answer = []
    
    time = 0
    stk = []
    
    index_time_list = []
    answer = []
    
    
    for i in range(len(prices)):
        while stk and stk[-1][0] > prices[i]:
            price, index = stk.pop()
            index_time_list.append((index, i - index))
        stk.append((prices[i], i))
    while stk:
        price, index = stk.pop()
        index_time_list.append((index, len(prices) - 1 - index))
    
    
    index_time_list.sort(key=lambda x : x[0])
    for i, time in index_time_list:
        answer.append(time)
    
    
    return answer

 

 

---