프로그래머스 스택/큐 주식가격 파이썬(list queue와 deque) - jimoo

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

 

코딩테스트 연습 - 주식가격

 

이번 문제는 어렵지 않습니다! 근데 효율성 부분에서 알려드릴 점이 있어서 포스팅하게되었습니다~~

 

처음에 시도한 방법 

def solution(prices):
    answer = []
    while(prices):
        count = 0
        now = prices.pop(0)
        for k in prices:
            count+=1
            if now>k:
                break
        answer.append(count)
            
            
    return answer

큐 방식으로 문제를 풀었었습니다!!! 큐는 list.pop(0)을 사용해 구현했었습니다.

그런데!! 테스트케이스는 다 통과했었지만 효율성 부분에서 런타임 에러가 뜨더라구요....

그래서 알아보았더니 list.pop(0)를 사용하여 큐를 구현하는 것 보다

deque.popleft() 으로 구현하는게 시간 복잡도가 낮다고 합니다. 

 

자세하게는 알아보지 않았는데

list.pop(0)은 시간복잡도가 o(n)

deque.popleft()은 시간복잡도가 o(1)

라고 하여 deque가 더 효율적이라고 합니다. (다음에 더 알아본 후 포스팅 다시 하도록 하겠습니다!!!)

 

실제로 list->deque로 변경해보니 런타임에러가 뜨지않는걸 볼 수 있었습니다.

 

deque로 시도한 코드

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while(prices):
        count = 0
        now = prices.popleft()
        for k in prices:
            count+=1
            if now>k:
                break
        answer.append(count)
            
            
    return answer