[프로그래머스] 주식가격 C++ 풀이

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

프로그래머스

 

풀이 방법

스택에 항상 주가가 오름차순이 되게 시점을 넣을 것이다.

그러므로, 스택의 top에는 항상 최고가가 들어있을 것이다. 이 최고가는 하락장을 겪지않은 가격이다. 

 

만약 현재 시점에서의 가격이 스택의 top보다 작다면?

그것은 하락장의 시작인것이다. 이때 스택을 뒤져서 손실이 난 가격들을 찾아 낼 수 있다.

이때 손실이 난 가격들은 현재 시점과 손실이난 가격의 시점의 차이를 이용하여

가격이 떨어지지 않은 기간을 구할 수 있다.

 

반복문이 끝났는데도 스택에 요소들이 남아 있을 수 있다.

이 요소들은 하락장을 겪지않은 요소들로 상승만 한 가격이다.

이 요소들은 마지막 시점(prices.size()-1)과 이 가격의 시점의 차이가 떨어지지 않은 기간이 된다.

 

전체 코드

#include <string>
#include <vector>
#include <stack>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size()); // prices 크기만큼 answer을 초기화 한다.
    stack<int> s;
    
    for(int i=0; i<prices.size()-1; i++){ // 마지막 price는 뭘해도 0초이니 제외하고 반복문 실행.
        while(!s.empty()&&prices[i]<prices[s.top()]){ // 하락장이라면
            answer[s.top()] = i-s.top(); // 기간은 현재 인덱스 i와 top()의 인덱스 차이가 된다.
            s.pop(); // top의 기간을 구했으니 pop.
        }
        s.push(i); // i를 push. 인덱스 i는 최고 가격이 된다.
    }
    
    /* 스택에 남은 원소들 처리 */
    while(!s.empty()){ // 스택에 남은 것들은 항상 상승만 했기에
        answer[s.top()] = (prices.size()-1)-s.top(); //맨 끝 위치에서 top을 빼줘서 끝까지 상승기간 구함. 
        s.pop();
    }
    answer[prices.size()-1]=0; // 마지막 price는 항상 0이 나옴.
    
    return answer;
}