title: "[프로그래머스] 주식가격 Python 파이썬 해설 (Level 2) - 이도훈"
cleanUrl: "programmers/42584"
description: "프로그래머스 Level 2 문제 [주식가격]의 풀이를 정리합니다."
# queue.PriorityQueue는 시간 초과입니다.
from heapq import heappush, heappop
def solution(prices):
answer = [-1] * len(prices)
# (가격, 시점)을 원소로 하는 max heap을 하나 관리합니다.
q = []
# 가격을 순회하면서,
for now, price in enumerate(prices):
# max heap 내에서 price보다 큰 가격을 가지는 원소들에 대해서 처리를 수행합니다.
while len(q) > 0 and -q[0][0] > price:
_, t = heappop(q)
# 만약 작다면, 해당 시점의 가격은 now - t만큼 떨어지지 않은 것입니다.
answer[t] = now - t
# max heap으로 동작하게 하기 위해서 -price를 넣어줍니다.
heappush(q, (-price, now))
# 끝까지 가격이 떨어지지 않은 원소들에 대해서 처리해줍니다.
now = len(prices) - 1
while len(q) > 0:
_, t = heappop(q)
answer[t] = now - t
return answer
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges