[프로그래머스] 주식가격

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

풀이

문제를 읽자마자 이중포문으로 하나씩 비교하는 방법을 생각했다.
스택/큐에 분류되어 있는 문제라 '설마 이 방법이 맞나?'라는 생각 때문에 선뜻 바로 풀어보지 않고 계속 다른 방법을 찾았다. 하지만 다른 방법이 생각나지 않아 그냥 처음 아이디어로 풀어봤다.
맞았다..!! (⭐️ 문제를 풀 때는 처음에 생각했던 방법 그대로 밀고 나가보자 ⭐️)
다른 풀이도 꼭 알아두자!

+) 스택으로 푸는 방법
인덱스를 스택에 저장하여 푸는 방법도 있다.
나중에 한번 더 풀어보자!!!

코드

처음 풀었던 풀이

#include <string>
#include <vector>

using namespace std;

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

stack 사용

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size() , 0);
    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);
    }
    // 이제 스택에 남아있는 인덱스 정리해주기 
    // prices 벡터가 끝날때까지 주식 가격이 떨어지지 않은 값들이다
    while(!s.empty()){
        answer[s.top()] = size - s.top() - 1;
        s.pop();
    }
    return answer;
}