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

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

프로그래머스

 

풀이

자기 뒤에서 자기보다 작은 가격이 등장한 최초의 순간만 찾으면 되는 간단한 문제라고 생각했는데......... .... 계속 시간초과가 나서 2시간정도 삽질하다가 해설을 봤다. deque 자료구조를 쓰거나 stack을 사용하면 되는 문제라고 한다. 

아래는 효율성 0점의 눈물나는 코드다.

# 단순 리스트 순회
def solution(prices):
    answer = []
    for i in range(len(prices)):
        cnt = 0
        for j in prices[i + 1 :]:
            if j < prices[i]:
                cnt += 1
                break
            else:
                cnt += 1
        answer.append(cnt)
    return answer

 

와 충격적... 알고리즘 오카방에 물어봤더니 알려줬다

for j in prices[i + 1 :]:

위 부분에서 매번 리스트를 새롭게 만들어주는 과정에서 시간초과가 난 것이다... 와 ... 그러고 보니 리스트 슬라이싱은 추출하여 새로운 리스트를 만들어주는 것이었다.... 그래서 이 부분 수정하면 효율성을 통과하기는 한다 대박사건

def solution(prices):
    answer = []
    for i in range(len(prices)):
        cnt = 0
        for j in range(i + 1, len(prices)):
            cnt += 1
            if prices[j] < prices[i]:
                break
        answer.append(cnt)
    return answer

리스트로 풀었을 때

---

deque 사용

list로 순회하는 방법에서 deque를 쓰는 방식으로 바꿨더니 바로 통과가 됬다. 분명 알고리즘은 똑같은데 이게 자료구조...?

# deque 사용
from collections import deque
def solution_deque(prices):
    queue = deque(prices)
    answer = []
    while queue:
        price = queue.popleft()
        cnt = 0
        for j in queue:
            cnt += 1
            if j < price:
                break
        answer.append(cnt)
    return answer

 

deque 라이브러리 사용 시

 

코드 실행 시간이 절반으로 줄었다... 더 효율적인 코드가 무엇일지 계속 고민하는 개발자가 되자