스택/큐 - 주식가격

C++

스택/큐 - 주식가격

문제

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

문제 출처

접근 방법

두 가지 방법으로 문제를 해결하였다.
처음에 stack을 사용하지 않고, 이중 for문을 이용하여 쉽게 해결하였다.
주식 가격이 마지막이 아니라면 최소한 1초는 가격이 떨어지지 않는다.
이후 나중의 주식가격을 비교해가며 몇 초동안 떨어지지 않는지 확인 한 후 결과 벡터에 저장하여 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int time = 0;                                   //주식 가격이 떨어지지 않으며 버틴 시간
    for (int i = 0; i < prices.size(); i++) {
        for (int j = i + 1; j < prices.size(); j++) {
            time++;                                 //1초간 가격은 떨어지지 않으므로, 비교하기 전에 증가한다.
            if (prices.at(i) > prices.at(j)) {      //만약 주식 가격이 현재 가격보다 떨어지는 순간이 오면 time를 증가시키는 것을 멈춘다.
                break;
            }
        }
        answer.push_back(time);                     //결과를 저장한다.
        time = 0;
    }
    return answer;
}

후기 및 개선할 점

2중 for문으로는 10분만에 해결이 가능하다.
하지만 문제 의도는 stack을 사용하여 풀어라 하였으므로, stack을 사용하여 푸는 방법을 고심하였다.

접근 방법 - stack

제일 중요한 것은 스택에 시간을 넣으며, 주식가격을 비교하고 가격이 떨어졌다면 스택의 시간과 현재 시간의 차이를 비교하는 것이다!!
출처

코드 - stack

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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