코딩테스트 : 주식가격

해당 문제는 i번째 인덱스가 언제까지 가격이 떨어지지 않는지 계산하는 문제이다.

지문이 이해하기 어렵게 되어있는데 쉽게 말해 0번째 인덱스가 몇 초 동안(인덱스 1당 1초) 현재 가격보다 크거나 같은 가격을 유지하는지 계산하는 문제이다.

 

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    //뒤에서 부터 하락 여부를 계산하기에 stack을 사용해 마지막에 순서 반전
    stack<int> s;
    
    //뒤에서 부터 계산하는데 앞에서 부터 계산해도 무방
    for(int i = prices.size() - 1; i >= 0; i--)
    {
		    //현재 인덱스와 다음 인덱스를 비교할때 몇번 이동했는지 저장할 변수
        int j = 1;
        //i = prices.size() -1, j = 1일 때 즉 가장 마지막 원소일때 가격 변화가 없으니 0
        if(i + j > prices.size() - 1)
        {
            s.push(0);
            continue;
        }
            
        //만약 범위를 벗어난다면 j만큼 가격이 떨어지지 않았다.
        //만약 가격이 떨어졌다면 현재 j만큼 가격이 떨어지지 않았다.
        while(i + j < prices.size() - 1 && prices[i + j] >= prices[i])
        {
            j++;
        }
        //현재 j만큼은 가격이 떨어지지 않음
        s.push(j);
    }
    
    //뒤에부터 계산 했기에 stack을 이용해 순서를 반대로 역전.
    while(!s.empty())
    {
        answer.push_back(s.top());
        s.pop();
    }
    
    return answer;
}

지금 생각해보니 stack을 사용하지 않고도 더 간단히 풀 방법이 있을 것 같다.