(프로그래머스) 주식가격

문제 링크

• 프로그래머스

요약

• 증감 추세가 바뀌는 지점을 찾는 문제에서는 stack을 사용하자.

최종 §

결과

• 이놈 와 같은 문제다. 증감 추세가 바뀌는 지점을 찾는 문제에서는 stack을 사용하자.

#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
struct PriceInfo {
	int idx;
	int price;
};
 
vector<int> solution(vector<int> prices) {
	stack<PriceInfo> stk;
	vector<int> ret(prices.size(), 0);
 
	for (int i = 0; i < prices.size(); i++) {
		auto price = prices[i];
		if (stk.empty()) {
			stk.push({i, price});
		} else if (stk.top().price <= price) {
			stk.push({i, price});
		} else /* stk.top().price > price */ {
			while (!stk.empty() && stk.top().price > price) {
				ret[stk.top().idx] = i - stk.top().idx;
				stk.pop();
			}
			stk.push({i, price});
		}
	}
 
	while (!stk.empty()) {
		auto &top = stk.top();
 
		ret[top.idx] = prices.size() - top.idx - 1;
		stk.pop();
	}
 
	return ret;
}