[C++][Programmers][스택/큐] 주식가격

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

---

*문제 설명

주식 가격이 나와있는 prices 벡터가 주어지고, 각 종목들이 몇초간 가격이 떨어지지 않았는지를 반환하면 된다.

stack/queue 문제에 있어서 본 자료구조를 활용해보려고 했지만 우선 어떻게 문제를 푸는지를 알기 위해 2중 for문으로 단순하게 구현했다.

 

* 알아둘 것

stack으로 푼 것.

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    int size = prices.size(); // 계속 size를 계산하는 것보다 상수값으로 저장하면 전체 함수 처리 시간 감소
    
    for (int i = 0; i < size; ++i){
        while (!s.empty() && prices[s.top()] > prices[i]){ // 가격이 줄어들었다면
            answer[s.top()] = i - s.top(); // 현재 시간 - 당시 시간
            s.pop();
        }
        s.push(i);
    }
    while (!s.empty()){
        answer[s.top()] = size - 1 - s.top(); // 종료 시간 - 당시 시간
        s.pop();
    }
    
    return answer;
}

 

* 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    for(int i = 0; i < prices.size(); i++){
        int time = 0;
        for(int j = i+1; j < prices.size(); j++){
            time++;
            if(prices[i] > prices[j]) break;
        }
        answer.push_back(time);
    }
    
    return answer;
}