주식가격

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

제한사항

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

입출력 예

코드

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

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    stack<int> s;
    for(int i = prices.size() - 1; i >= 0; i--) {
        stack<int> temp;
        while(!s.empty() && s.top() >= prices[i]) {
            temp.push(s.top());
            s.pop();
        }
        answer[i] = temp.size();
        if(!s.empty()) answer[i] += 1;
        while(temp.size() != 0 ){
            s.push(temp.top());
            temp.pop();
        }
        s.push(prices[i]);
    }
    return answer;
}

기타

스택을 이용해서 풀었다.

마지막 가격부터 확인하며, 스택 s에는 현재까지 확인한 가격들을 push.
스택 s에서 현재 가격보다 작은 원소를 만날 때까지 현재 가격보다 크거나 같은 원소는 pop하여 스택 temp에 담는다.
temp에 담긴 원소의 길이가 떨어지지 않은 시간을 의미하는데

• 스택 s가 비어있으면 끝까지 가격이 떨어지지 않았으므로 시간 = 길이
• 스택 s가 비어있지 않은 경우, 1초를 추가로 더해줘야한다. (떨어지지 않은 시간이 1초의 간격(?)을 유지하므로)