프로그래머스 42584 - 주식가격

정답 1 (최대 29.58ms)

#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++) {
        for (int j = i + 1; j < prices.size(); j++) {
            answer[i]++;

            if (prices[i] > prices[j])
                break;
        }
    }

    return answer;
}

💭 풀이
1. prices를 순회하면서 각 가격을 기준으로 이후 가격들을 확인
2. 다음 가격은 현재에서 시간이 1 지난 후이기 때문에 시간 증가를 먼저 처리
3. 가격이 떨어졌으면 break

정답 2 (스택 / 최대 26.42ms)

• 교재 풀이 참고

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

using namespace std;

vector<int> solution(vector<int> prices) {
    int sz = prices.size();
    
    vector<int> answer(sz, 0);
    stack<int> stk;
    
    for (int i = 0; i < sz; i++) {
        if (stk.empty() || (!stk.empty() && prices[i] >= prices[stk.top()])){
            stk.push(i);
        }
        else {
            while (!stk.empty() && prices[i] < prices[stk.top()]) {
                int top_idx = stk.top();
                answer[top_idx] = i - top_idx;
                stk.pop();
            }
            stk.push(i);
        }
    }
    

    while (!stk.empty()) {
        answer[stk.top()] = sz - stk.top() - 1;
        stk.pop();
    }
    
    return answer;
}

💭 풀이
1. 스택이 비어있거나, 가격이 안 떨어진 경우 stack에 push
2. 스택의 top 시점의 가격과 현재 시점의 가격을 비교
3. 가격이 떨어진 시점들은 모두 pop (현재 시점(i)의 가격 < skt.top 시점의 가격)
4. 현재 시점 i는 다시 push
5. 스택에 남아있는 시점들 처리

개선점

• if, else 생략 가능