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