[프로그래머스/C++] 주식가격 (스택/큐 연습)

주식가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

 

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

---

 해당 문제는 스택과 큐를 이용해서 배열 안에 원소가 어느 시간까지 감소되지 않는지를 찾는 문제였다.

 

#include <stack>
#include <vector>

using namespace std;

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

	st.push(0);

	for (int i = 1; i < prices.size(); i++)
	{
		while (!st.empty())
		{
			int top = st.top();
			if (prices[top] <= prices[i]) break;
			st.pop();
			answer[top] = i - top;
		}
		st.push(i);
	}

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

int main()
{
	vector<int> prices = { 1,2,3,2,3 };
	solution(prices);
}

 

나는 배열의 인덱스를 스택에 담아가며 비교하는 방법을 통해 문제를 풀이하였다.

 

 

풀이방법을 도식화한 그림은 위와 같다.

 

1. prices 배열 0번째 인덱스를 스택에 넣어두고, 1번째 인덱스부터 for문으로 비교를 시작하였다.

 

2. 스택의 top에 있는 원소가 다음 들어가는 숫자보다 작다면 스택을 pop하여 top을 제거하고, answer 배열의 top 인덱스의 원소값을 변경해주었다.

이때 answer 배열의 값은 현재 인덱스 값인 i에 top 인덱스 값을 빼서 몇 초 동안 가격이 떨어졌는지를 검사하였다.

 

위 예제에서는 2번째 인덱스 값인 3보다, 3번째 인덱스 값인 2가 더 작은 수이기 때문에, 2번째 인덱스를 제거하고 answer[2]에 3-2 = 1 값을 넣었다.

이후, 스택의 top인 1번째 인덱스값인 2는 3번째 인덱스 값인 2와 크기가 같기 때문에 더이상 진행하지 않고, 3번째 인덱스를 스택에 추가해주었다.

 

만약, 스택에 들어있는 top의 값이 계속 더 작다면, 3 - 1 = 2, 3 - 0 = 3 처럼 가격이 떨어진 시간이 점점 커지게 되어 answer 배열에 저장되는 것이다.

 

3. 모든 원소의 for문 검사가 끝났다면 스택이 비어있지 않을 때까지 while문을 돌면서 마지막 연산을 수행한다.

 

4. answer의 원소 중, 스택의 top에 해당하는 인덱스를 주식의 총 개수(prices.size())에서 top -1 하여, 가격이 떨어지지 않은 시간을 계산한다.

이전에 answer에는 몇 초 동안 가격이 떨어지는지를 담아놨으니, 반대로 가격이 떨어지지 않은 시간을 구하기 위해 전체 값에서 해당 시간을 빼는 것이다.

 

중간에, 가격이 떨어져서 answer를 초기화 시켰던 answer[2]의 경우엔, 스택에서 pop하여 인덱스를 뺐었기 때문에 재정의되지 않고 저장했던 그대로 나오게 된다.

---

처음엔 prices 배열에 있는 주식의 가격들을 기반으로 2중 for문으로 전부 비교해야 하나 싶었는데, 인덱스 계산만으로 문제가 풀릴 수 있었다. 생각과 접근의 전환이 되는 문제였던 것 같다.

---

https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=cpp

프로그래머스