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

문제

문제 설명

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

제한사항

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

입출력 예

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

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

풀이

#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
struct Stock {
    int idx, price;
    
    Stock (int idx, int price)
        : idx(idx), price(price) {}
};
 
vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0); // 동일한 크기의 배열로 초기화
    // 이중 for 문으로 구현하기
    
    // stack 사용해서 구현하기
    // 스택에 값을 넣는다
    // 스택의 top값과 다음에 넣어줄 값을 비교합니다.
    // 만약 top에 있는 값이 더 작거나 같다면, 가격이 상승/유지한 것이므로 값을 스택에 추가합니다.
    // 만약 top에 있는 값이 더 크다면, 가격이 하락한 것으로 pop을 하고, 몇 초 뒤에 하락한 것인지 계산합니다. 이것을 top에 있는 값이 현재 값보다 작은 것이 나올 때까지 반복합니다.
    stack<Stock> s;
    for (int i=0; i<prices.size(); i++) {
        while (!s.empty()) {
            Stock prev = s.top();
            if (prev.price <= prices[i]) { // 가격 상승
                s.push(Stock(i, prices[i]));
                break;
            }
            else { // 가격 하락
                s.pop();
                answer[prev.idx] = i-prev.idx;
            }
        }
        s.push(Stock(i, prices[i]));
    }
    
    // 스택에 남아있는 것들은 끝까지 가격이 하락하지 않았음.
    while(!s.empty()) {
        int total_time = prices.size()-1;
        answer[s.top().idx] = total_time - s.top().idx;
        s.pop();
    }
    
    return answer;
}