[프로그래머스/level2/c++] 주식 가격 - "스택/큐"

문제 :

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

 

제한사항 :

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

입출력 예 :

prices	return
[1,2,3,2,3]	[4,3,1,1,0]

 

코드 :

-이중 for문을 썼을 때

#include <string>
#include <vector>

using namespace std;

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

-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();
    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-s.top()-1;
        s.pop();
    }
    return answer;
}

 

다시 한번 짚고 넘어가기 :

-코드 리뷰

stack을 쓴 코드는 다른 사람의 정답 코드를 참고하여 작성한 코드이다.

이중 for문을 쓰면 시간복잡도가 비효율적인것 같아서 코드에 대한 고민을 많이 하였고 stack을 어떻게 이용할지 바로 생각이 나지않았다.

stack에 prices의 index를 넣는 다는 점, pop조건을 stack의 top와 for문을 돌고있는 i와 비교하는 점과

if문이 아닌 while문사용, 마지막 while문은 가격이 떨어지지 않은 index를 고려한 점 등 이것들에 대한 알고리즘을 배우게되었다.