문제 설명 및 제한사항
아이디어 및 해결 방법
코드
# 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
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges