Programmers - 주식 가격

문제 링크

처음에는 각 초 별로 이후 시간들을 전부 순회하는 방법을 생각했었는데, 길이가 100,000 이하인 것을 확인하고 다른 방법을 생각해야 했다.

가격이 떨어지지 않을때 큐에 하나씩 넣다가 가격이 떨어진 경우 큐를 순회하여
가격이 떨어지지 않은 시간을 계산 후 큐에서 제거하는 방식을 사용했다.

def solution(prices):
    q = []
    answer = [0 for i in range(len(prices))]

    for (time, price) in enumerate(prices):
        # 가격이 떨어지지 않은 경우
        if len(q) == 0 or q[-1][1] <= price:
            q.append((time, price))
            # print("add", time, price)
            continue

        # 가격이 떨어진 경우
        while True:
            if len(q) == 0:
                q.append((time, price))
                break

            (queued_time, queued_price) = q[-1]
            # print("queued: ", queued_time, queued_price, " current : ", time, price)
            if queued_price > price:
                q.pop()
                answer[queued_time] = time-queued_time
            else:
                q.append((time, price))
                break

    # 끝까지 떨어지지 않은 가격들 처리
    for (queued_time, queued_price) in q:
        answer[queued_time] = (len(prices)-1) - queued_time

    return answer