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

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

프로그래머스

스택을 이용하면 효율적으로 풀 수 있는 문제.

가격이 떨어지지 않는 동안 스택에 가격 정보를 담아두고 가격이 떨어지면 스택을 pop하는 방식으로 풀면 된다.

 

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

using namespace std;

vector<int> solution(vector<int> prices) {
	vector<int> answer(prices.size());

	stack<pair<int, int>> price_stack;

	price_stack.push(make_pair(0, prices[0]));

	int i;
	for (i = 1; i < prices.size(); i++) {
		while (!price_stack.empty() && prices[i] < price_stack.top().second) {
			int sec = price_stack.top().first;
			int price = price_stack.top().second;

			answer[sec] = i - sec;

			price_stack.pop();
		}

		price_stack.push(make_pair(i, prices[i]));
	}

	while (!price_stack.empty()) {
		int sec = price_stack.top().first;
		int price = price_stack.top().second;

		answer[sec] = i - sec - 1;

		price_stack.pop();
	}

	return answer;
}

 

처음에 내가 작성했던 풀이.

스택에 초와 가격의 쌍을 저장하기 위해 pair를 사용했다.

이렇게 풀어도 답이 잘 나오긴 하는데, 다른 사람들의 풀이를 보니 스택에는 초만 쌓아두고 초에 해당하는 가격은 prices 리스트에서 불러오는 방식으로 푸는 것을 보았다. 이렇게 푸니 코드가 훨씬 간단해진다.

 

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

using namespace std;

vector<int> solution(vector<int> prices) {
	vector<int> answer(prices.size());

	stack<int> s;

	int size = prices.size();

	for (int i = 0; i < prices.size(); i++) {
		while (!s.empty() && prices[i] < prices[s.top()]) {
			answer[s.top()] = i - s.top();
			s.pop();
		}

		s.push(i);
	}

	while (!s.empty()) {
		answer[s.top()] = size - s.top() - 1;
		s.pop();
	}

	return answer;
}

 

최종 코드.

스택을 사용하지 않아도 풀 수는 있으나 시간복잡도가 커진다.

 

3.28에 있는 모의 코딩테스트를 응시해놔서(아직 제대로 풀기엔 실력이 노답이긴 하지만) 프로그래머스에 익숙해질 필요가 있다. 당분간은 프로그래머스 문제를 푸는 것으로!