[프로그래머스 알고리즘 Kit] 스택/큐 - 주식가격

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

프로그래머스

 

문제설명

 

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하는 것이다. 

 

 

 

제한사항

 

prices의 길이는 2 이상 100,000 이하이다.

 

 

 

 

구현1

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

위와 같이 구현하였을 때 올바르게 리턴은 되지만 효율성 테스트 모두 실패하였다. 효율성 있는 코드를 구현하려면 시간복잡도 O(10^12)을 보통 넘기면 안된다. 

위 문제에서 주어진 제한사항을 보면 시간복잡도에 관여되는 prices의 길이가  2이상 10^5이하로 O(n^2)을 풀게된다면 최악의 시간복잡도가 O(n^12)이기 때문에 효율성 테스트에서 간당간당하게 실패한 포인트를 찾아야한다. 

 

따라서, 이를 개선해보겠다. 

 

 

구현2

from collections import deque #deque 사용

def solution(prices):
    answer = []
    temp = deque(prices) #deque 사용
    while len(temp) > 0:
        price = temp.popleft() #deque 메소드 사용
        count = 0
        for item in temp:
            count += 1
            if price > item:
                break
        answer.append(count)
    return answer

list의 pop(0)의 경우 복잡도가 O(n)으로 2중 반복문으로 구현하여 O(n^2)에서 O(n)연산이 추가되었기 때문에 효율성 테스트에서 실패했던 것이다. 

 

이때, 활용하기 좋은 것이 파이썬에서 제공하는 deque이다. 이를 사용하시면 O(1)의 복잡도로 popleft() 왼쪽에서의 첫번째 원소를 뽑아올 수 있어 시간복잡도가 줄어든다. 

 

아래의 wiki를 참고하자.

 

https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki