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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42584?language=cpp 

코딩테스트 연습 - 주식가격

1. 주의할 점

- Stack을 이용하여 해결한다

 

2. 구현

- Stack에 Prices의 인덱스를 담는 방식으로 진행한다

- Stack의 Top의 원소에 해당하는 Prices보다 현재 Prices(val)가 크거나 같으면 Stack에 추가한다

- 아니라면 Stack의 원소를 뽑아내여 Arr[] 배열에 주식이 내려가지 않은 기간을 저장한다

- For문이 끝나더라도 Stack에 원소가 남아있을 수 있으니, Stack의 전체가 빌때까지 모든 원소를 뽑아내어 Arr[] 배열을 채운다

#include <string>
#include <vector>
#include <stack>
using namespace std;
int arr[100000];

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int len = prices.size()-1;
    stack<int> s;
    
    for(int i=0;i<=len;i++){
        int val = prices[i];
        while(!s.empty()){
            int cidx = s.top();
            int cv = prices[cidx];
            if(cv<=val)   break;
            else{
                arr[cidx] = i-cidx;
                s.pop();
            }
        }
        s.push(i);
    }
    while(!s.empty()){
        int cidx = s.top();
        s.pop();
        arr[cidx]=len-cidx;
    }
    for(int i=0;i<=len;i++)
        answer.push_back(arr[i]);
    return answer;
}