문제 푼 날짜 : 2021-10-04

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42584

접근 및 풀이

문제를 봤을 때, 완전탐색으로 접근하면 쉽게 풀 수 있다. 실제로 테스트 통과가 되긴 되는데, 아마도 입력값이 작아서 인 것 같다. 이런 코드는 입력이 더 커지면 시간초과가 날 것이 분명하다.
좀 더 효율으로 구현하기 위해서 고민하다가 스택을 이용해야겠다고 생각했다.
처음에 스택에 주식 가격을 넣어주면서 얼마나 스택에 오래 있었는지를 찾아주려다가 대실패를 하고, 생각을 바꿔 주식 가격의 인덱스쪽으로 접근을 해보았다.
주식 가격을 하나씩 탐색하며 가격이 상승하면 계속 넣어주다가 가격이 하락했을 때, 가격 하락에 영향받는 인덱스들을 뽑아내어 몇 초간 가격이 떨어지지 않았는지 계산해주었다.

코드(완전탐색)

#include <string>
#include <vector>

using namespace std;

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

코드(스택)

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> st;
    
    for (int i = 0; i < prices.size(); i++) {
        while (!st.empty() && prices[st.top()] > prices[i]) {
            answer[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    
    while (!st.empty()) {
        answer[st.top()] = prices.size() - st.top() - 1;
        st.pop();
    }
    return answer;
}

결과

피드백

매번 문제를 풀 때마다 가장 효율적으로 짤 수 있다면 얼마나 좋을까...