[Algorithm] 프로그래머스 C++ : 주식가격

 

 

 

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

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

 

그냥 for문 두개 돌려서 비교하는데, break; 조건을 줘서 시간을 줄였다.

 

 

Code

#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(); i++) {
        
        for(int j=i+1; j<prices.size(); j++) {
            answer[i]++;
            if(prices[i] > prices[j]) break;
        }
    
    }
    
    return answer;
}

 

 

카테고리가 '스택/큐'라서 스택을 이용하는 방법을 찾아봤다.

index가지고 스택에 넣는게 신기하다..

 

중간에 감소하는 부분이 있는 index 요소만 for 문에서 answer가 결정되고

감소하는 부분이 없는 애들은 맨 마지막 while문에서 answer가 정해진다.

 

 

Code

#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;
}