[C++ ] 프로그래머스 45284번 주식가격

프로그래머스 45284번 주식가격 - Stack and Queue - Level 2

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

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

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때,

가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

 

Mine

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {

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

 

the another way (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에는 모든 인자의 주식값을 넣는데, 

혹시 중간에 혹시 떨어지는 값의 인자는 미리 초계산을 하고 스택에서 빼버림.
Stack에 마지막 까지 있는 인자들은 끝날때까지 내려가는 일은 없는 값들이므로 Size-s.top()-1으로 고정.

 

 

Key Point 🔑

 

문제 이해도만 있으면 별로 안어려움.
O(n^2)보다 빨리 하려 하다가 늦어짐.
내가 푼 풀이로 푸는것이 나을듯함

🔑 내려가는 일이 없는 값들은 Size-s.top()-1으로 고정 이란건 의미가 있어보임