[프로그래머스/C++]Lv.2 - 주식가격

문제 링크

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

내 풀이

배열을 미리 선언해두고 이중for문으로 각 원소마다 더 작은 숫자가 나올때까지 검사해가면서 arr[i]++을 한다.
다 나왔으면 answer에 옮긴다.

내 코드

#include <string>
#include <vector>

using namespace std;

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

다른 사람의 풀이

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

다른 사람의 풀이 해석

stack에 인덱스를 저장하는 방식을 사용했다.
stack이 비어있거나 스택의 top의 값이 현재 prices[i]이하면 i를 push하고
비어있지 않고 stack의 top의 값이 prices[i]보다 크면 ( 주가가 떨어졌다면 )
answer[s.top()]에 초를 계산해서 넣어준다.
이 작업은 중간에 주가가 떨어지는 때가 있는것들을 검출해낸다.
그다음 while에선 끝까지 떨어지지않은것들을 시간을 계산해서 answer에 넣어준다.