❓프로그래머스 : 주식가격
〽️ 문제 요약
초 단위로 기록된 주식가격이 주어질 때, 각 초마다 가격이 떨어지지 않은 기간은 몇 초인지를 구하면 되는 문제
🤨 접근법
완전 탐색으로 O(n^2)만에도 풀리는 문제이지만 문제의 유형이 스택/큐를 활용하는 문제이기 때문에 스택/큐를 활용해서 효율성을 높혀보고자 했다.
예시에서 처럼 주식 가격이 [1, 2, 3, 2, 3]으로 주어지는 경우 우선 처음 증가하는 부분 까지의 인덱스를 스택(upper)에 담는다. 그려면 스택의 상태는 [0, 1, 2]으로, 3다음으로 2가 나옴으로서 증가가 멈췄다.
이 때 스택에서 하나씩 꺼내보면
- 3번째 인덱스의 값에 해당하는 2는 2번째 인덱스의 값에 해당하는 3은 보다 작아 증가가 멈춤 → 3-2 = 1초 증가한다.
- result[2] = 1
- 3번째 인덱스의 값에 해당하는 2는 1번째 인덱스의 값에 해당하는 2와 같아 가격이 떨어진 건 아님 →스택에서 꺼내지 않고 보류한다.
다음 증가하는 부분인 2, 3도 스택에 담아서 최종적으로 스택의 상태는 [0, 1, 3, 4]로 스택에 남아있는 값들은 끝날 때까지 가격이 떨어지지 않은 것이다. 따라서 len(prices)-1 초에서 각 초까지의 텀이 떨어지지 않는 기간이다.
while upper:
j = upper.pop()
answer[j] = (len(prices)-1)-j스택의 LIFO 구조를 이해하고 활용할 줄 알아야 가능한 풀이이다.
🔡 코드
from collections import deque
def solution(prices):
answer = [0 for _ in range(len(prices))]
upper = deque()
for idx, price in enumerate(prices):
while upper and price < prices[upper[-1]]:
j = upper.pop()
answer[j] = idx-j
upper.append(idx)
while upper:
j = upper.pop()
answer[j] = (len(prices)-1)-j
return answer📚 고찰
너무 큐 활용에만 익숙해져있는 것 같다. 자료구조를 활용할 때 큐를 활용한 풀이가 생각나지 않으면 스택으로 접근하여 풀이법을 생각해보자.
Grow Exponentially