[프로그래머스/Level 2] 주식가격 (C++)

programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

 

풀이

 

해당 문제는 Stack을 이용해서 풀 수 있는 문제입니다.

단순히 2중 반복문을 이용해서 문제를 해결하면 입력값의 최대가 100,000 이므로 시간초과가 발생합니다. (근데 프로그래머스에서는 그냥 정답으로 처리해버립니다... 테스트 케이스가 허술한듯?) 따라서 스택을 이용해서 문제를 해결해야하는데, 그러면 선형 복잡도 O(N)으로 해결할 수 있습니다. 인덱스(시간)을 스택에 넣으면서 앞의 값이 뒤의 값보다 큰 경우(주식이 떨어지는 부분)를 고려해주는 것이 포인트

 

/* Stack 풀이 */

#include <string>
#include <vector>
#include <stack>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    
    for(int i=0;i<prices.size();i++) {
    	// 앞의 값이 뒤의 값보다 큰 경우를 고려해준다.
        // 위의 경우가 있을 경우, 이후에도 계속 떨어지는지 확인하기 위해 while 사용
        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()]=prices.size()-s.top()-1;
        s.pop();
    }
    
    return answer;
}