프로그래머스 / 주식가격

https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=cpp

프로그래머스

 

계속 가격이 하락하지 않을때마다 인덱스를 쌓고 가격이 하락하면 뒤에서 인덱스를 제거해야 하므로 스택을 사용해 해결했다

    stack<int> s;
    s.push(0);

추가로 첫번째 인덱스를 스택에 추가했다

    for (int i = 1; i < prices.size(); i++)
    {
		// 현재 가격보다 높은 이전 가격(스택에 저장된 인덱스)인 경우 유지시간을 answer에 기록하고 스택에서 제거
        while (!s.empty() && prices[s.top()] > prices[i])
        {
			// 유지된 가격의 기간 = 현재 인덱스 - 스택에 저장된 인덱스
            answer[s.top()] = i - s.top();
            s.pop();
        }

		// 현재 인덱스를 스택에 저장
        s.push(i);
    }

첫번째 인덱스는 추가되어있어 for문의 i는 1부터 시작했다

while문으로 현재 인덱스와 스택에 저장된 마지막 인덱스의 가격을 비교하여 가격이 내려간 경우 answer에 유지된 가격의 기간을 저장하고 pop한다

while문이 끝나면 현재 가격보다 높은 가격들은 모두 제거되었으므로 현재 인덱스를 스택에 추가한다

 

    while (!s.empty())
    {
        answer[s.top()] = (prices.size() - 1) - s.top();
        s.pop();
    }

이제 한번도 감소된 적 없는 인덱스들이 스택에 남아있기 때문에 마지막 인덱스까지 유지된 기간을 answer에 저장한 뒤 pop 한다

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());

    // 아직 가격이 하락하지 않은 인덱스를 저장할 스택
    stack<int> s;
    s.push(0);

    for (int i = 1; i < prices.size(); i++)
    {
		// 현재 가격보다 높은 이전 가격(스택에 저장된 인덱스)인 경우 유지시간을 answer에 기록하고 스택에서 제거
        while (!s.empty() && prices[s.top()] > prices[i])
        {
			// 유지된 가격의 기간 = 현재 인덱스 - 스택에 저장된 인덱스
            answer[s.top()] = i - s.top();
            s.pop();
        }

		// 현재 인덱스를 스택에 저장
        s.push(i);
    }

	// 스택에 남은 인덱스는 끝까지 가격이 하락하지 않은 경우이므로 유지 시간을 계산하여 answer에 기록
	// 마지막 인덱스는 prices.size() - 1이므로
    // 유지 시간은 (prices.size() - 1) - 현재 인덱스가 된다
    while (!s.empty())
    {
        answer[s.top()] = (prices.size() - 1) - s.top();
        s.pop();
    }

    return answer;
}