주식가격

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

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

 

내가 쓴 답안:

from collections import deque

def solution(prices):
    answer = [0 for _ in range(len(prices))]
    prices = deque(prices) # 디큐로 넣기
    
    pre = prices.popleft() # 맨 처음 값 가져오기
    i=0

    while prices:
        cnt = 0
        for pre_idx, others in enumerate(prices):
            answer[i] += 1
            if((pre > others) or (pre_idx==len(prices)-1)): # 마지막이거나 가격이 떨어지면 조건문 들어가기
                pre = prices.popleft()
                i += 1 # 다음 날짜 기준으로 이동
                break

    return answer

 

베스트 답안:

def solution(prices):
    answer = [0]*len(prices)
    stack = []
 
    for i, price in enumerate(prices):
        #stack이 비었이면 false
        while stack and price < prices[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
 
    # for문 다 돌고 Stack에 남아있는 값들 pop
    while stack:
        j = stack.pop()
        answer[j] = len(prices) - 1 - j
 
    return answer


출처: https://deftkang.tistory.com/175 [deftkang의 IT 블로그]

 

짧은 후기:

처음에 while이랑 for로 하고 했더니 답은 다 맞는데 효율성이 0이 나왔다.

왜 그런지 찾아보니, 스택이라고 생각하고 price를 넣은 뒤 .pop(0)으로 첫번째를 뽑는 곳에서 시간 복잡도가 O(n)이 나와버렸다. 알고보니 뽑되, 빈 자리를 채우려고 앞으로 당기다보니 그런 것..!

 

그래서 디큐로 넣고 popleft()를 썼다.

 

이번 문제를 통해 시간 복잡도의 중요성과 웬만하면 pop(0)을 쓰지 말것을 깨달았다.