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

프로그래머스

 

📄 문제

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

 

📝 풀이

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

using namespace std;

vector<int> solution(vector<int> prices) {
    int n = prices.size();
    vector<int> answer(n, 0);
    stack<int> s;
    
    // 모든 값 검사
    for(int i = 0; i < n; ++i)
    {
        // s가 비어있지 않을때, 
        // top의 가격이 prices[i]보다 크다면 가격이 떨어지기 시작
        while(!s.empty() && prices[s.top()] > prices[i])
        {
            // answer[s.top()]에는 현재 위치(i) 에서 삽입한 위치(s.top)의 차이를 삽입
            answer[s.top()] = i - s.top();
            s.pop();
        }
        
        // 현재 위치 삽입
        s.push(i);
    }

    // 해당 위치의 가격은 마지막까지 한번도 떨어지지 않은 경우임
    // s가 빌때까지 모두 정답에 삽입
    while(!s.empty())
    {
        answer[s.top()] = n - s.top() - 1;
        s.pop();
    }
    
    return answer;
}

• 스택을 이용하여 문제를 해결하였습니다.
• i를 지속적으로 push하면서 가격이 직전 가격보다 떨어지는지 검사합니다.
• 만약, 가격이 떨어진다면 가격이 떨어지지 않는 경우까지 계속 정답에 삽입한 후, s의 값을 pop 합니다.