[프로그래머스] 주식 가격

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

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

 

일단 문제 해석이 어색하게 될 수 있어서 좋은 문제는 아니라는 생각이 든다.

질문을 검색하면 다른 사람들도 문제 이해에 많은 혼란을 겪은 듯 하다.

 

문제에서 주식 가격이 바로 다음 순간에 바뀌더라도, 1초간 가격이 변동되지 않았다는 것으로 간주해야 한다는 점이 포인트이다.

즉, 다음 원소가 더 작은지 여부를 판단하기보단 가격이 떨어지기 전 까지의 '간격의 개수'를 찾는 문제였다.

 

처음 풀이에서 정확성 테스트는 모두 통과가 되었는데, 효율성이 모두 빵점이 나왔다.

 

이전까지는 큐를 이용해야 할 때 collections 패키지의 deque를 사용했었는데, 이번 문제에서 리스트의 pop(0) 메소드를 이용한 것이 문제였다.

 

리스트의 pop() 메소드는 원하는 인덱스까지 찾아간 후 pop을 하기 때문에 최대 O(n)의 시간 복잡도를 가지고 deque의 popleft() 의 경우에는 O(1)을 가지기 때문이다.

 

어차피 이 문제에서는 리스트를 큐 처럼 사용하기 때문에 pop을 사용해도 1의 시간이 걸릴거라고 생각했는데 아니었다...

 

from collections import deque

def solution(prices):
    result = list()
    q = deque()
    
    for i in prices:
        q.append(i)

    while q:
        count = 0
        temp = q.popleft()
        for i in q:
            count += 1
            if temp > i:
                break
        result.append(count)
    
    return result