[프로그래머스] 주식가격 C++

1. 문제 설명

• 문제 바로가기

---

2. 풀이 과정

• 문제 해결의 흐름 
  1. 처음에 문제 자체를 이해하는데 어려움이 있었다-! 
  2. 자세히 살펴보니 입력된 주식가격(prices)이 언제까지 떨어지지 않는지 구해주면 되는 것이었다.
  3. 이때, 주식 가격이 입력되는 간격은 1초이다.
  4.  입력된 가격 배열 prices를 순회하며 이전에 살펴봤던 값이랑 비교하였을 때 현재 값이 이전 값보다 더 작다면 이전 값의 가격이 하락한 것이기에 가격 하락 전까지의 기간을 배열에 저장해주자!
  5. 4.에 해당하지 않는 값들은 Stack에 계속 쌓아준다.
  6. 4.~5.의 과정이 끝난 이후 Stack에 있는 값들을 pop하며 배열에 저장한다.

• 코드 

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    stack<pair<int,int>> S;
    
    for (int i = 0; i < prices.size(); ++i) {
        int curVal = prices[i];
        
        while(!S.empty() && S.top().first > curVal) {
            int price = S.top().first;
            int idx = S.top().second;
            S.pop();
            answer[idx] = i - idx;                                                           
        }
        
        S.push(make_pair(curVal,i));
    }
    
    while (!S.empty()) {
        int price = S.top().first;
        int idx = S.top().second;
        S.pop();
        answer[idx] = prices.size() - 1 - idx;
    }
    
    return answer;
}

 

---

3. 후기 

 for문 하나로만 모든 것을 다 하려고 하지 말고 크게 2가지 틀로 나누어 살펴보면 쉽게 풀 수 있는 문제!