프로그래머스 - 주식가격 - C++

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

프로그래머스

 

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

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    stack<pair<int,int>> s;
    map<int,int> m;
    
    for(int i=0;i<prices.size();i++)
    {
        if(s.empty())
            s.push({i,prices[i]});
        else if(s.top().second<=prices[i])
            s.push({i,prices[i]});
        // 가격이 떨어진경우
        else
        {
            while(!s.empty() && s.top().second>prices[i])
            {
                auto& item = s.top();
                m[item.first]=i-item.first;
                s.pop();
            }
            s.push({i,prices[i]});
        }
    }
    while(!s.empty())
    {
        auto& item = s.top();
        m[item.first]=prices.size()-1 - item.first;
        s.pop();
    }
    for(auto& item : m)
        answer.push_back(item.second);
    return answer;
}

prices 배열의 각 원소에는 1초마다의 주식가격이 들어있다. 

그 초마다의 가격이 떨어지기까지의 시간을 계산해서 반환한다.

ex) 1,2,3,2,3 이면

3초까지는 1,2,3 으로 계속 오른다. 

4초때는 3->2로 가격이 떨어진다. 

그렇다면 3초시점의 가격은 1초 뒤 떨어지므로 

answer[2] = 1 이 된다. [2]인 이유는 인덱스 0부터 시작이기 때문.

 

스택과 맵을 통해서 접근해보았다. 

스택과 맵에서 사용할 아이템을 <int,int> 로 잡고 first에는 시점 즉 i를 저장하고 second에는 떨어지기까지의 시간을 저장한다. 

stack에 저장할 때, 다음 가격이 오르면 계속 쌓고 만약 가격이 떨어지면 스택에서 꺼내서 맵에 몇초간 유지했는지 계산해서 저장한다. 

가격이 떨어진 경우의 while문은 현재시점의 가격이 떨어진 가격이 되는 경우가 i-1만 있는것은 아닐 수 있기 때문이다. 

 

마지막으로 스택에 남아있는 가격들을 map에 옮긴다. 

 

이 때, map에는 자동으로 first를 기준으로 정렬을 해주기 때문에 마지막에 순서대로 꺼내서 answer에 저장하면된다.