[프로그래머스] 주식가격(파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

눈물나는 주식을 알고리즘 문제로 낸 사악한 문제.

주식차트를 간단하게 그려봅니다.

주식의 현재값들을 계속 큐에 넣어주고

현재 가격과 비교를 하는 식으로 코드를 구성할 수 있습니다.

그런데, 그렇게 코드를 짜면 시간초과가 발생합니다.

왜냐하면 큐 전체를 다 돌아야하기 때문에

시간이 많이 소요가 될 수 밖에 없습니다.

 

근데 다시 생각해보면

모든 큐를 다 돌 필요가 없습니다.

현재 큐에서 가장 가격이 높은 것부터 비교해주면 됩니다.

우선순위큐로 가격이 높은 것부터 차례대로 담으면서

현재가격보다 높은 가격인지 계속 판단해주면서 pop해줍니다.

반복이 끝났으면

현재 큐에 있는 데이터값들에

idx값들에 +1씩 더해주면 됩니다.

 

from heapq import *


def solution(prices):
    answer = [0]*len(prices)
    q=[]
    for i in range(len(prices)-1):
        now=prices[i]
        heappush(q,(-now,i))

        while q[0][0]*(-1)>now:
            p,idx=heappop(q)
        for g,idx in q:
            answer[idx]+=1
        # print(q)
        # print(answer)
    return answer