주식가격

문제설명

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

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

접근방법

맨 위에 것보다 낮은 값들(기간 결정되기를 기다리는 애들)만 관리되는 스택을 만들자

how? 스택에 주가 하나씩 넣으면서 이번에 들어가는 주가에 의해
기간(떨어지지 않은)이 결정되는 과거 주가들을 스택에서 빼준다.

코드

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

struct jusic{
    int v, s;//value second
    jusic(int vv,int ss){
        v = vv;s = ss;
    }
};

int tab[100000]={0};
void pop_while(stack<jusic> &s, jusic chell){//chell보다 더 작은 숫자로 구성된 스택만들때까지
    if(s.empty()){
        return;
    }
    if(s.top().v <= chell.v){
        return;
    }
    jusic s_top = s.top();
    s.pop();
    tab[s_top.s] = chell.s-s_top.s;
    pop_while(s,chell);
}

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    stack<jusic> s;
    for(int i =0;i<prices.size();i++){
        jusic cur = jusic(prices[i],i);
        pop_while(s, cur);//empty 처리함
        s.push(cur);
    }
    while(!s.empty()){
        jusic cur = s.top();
        s.pop();
        tab[cur.s] = prices.size()-1-cur.s;
    }
    for(int i =0;i<prices.size();i++){
        answer.push_back(tab[i]);
    }
    return answer;
}