주식가격

문제

문제

 

처음 작성한 코드 // 효율성 통과 X

def solution(prices):
    answer = [0]*len(prices)
    for idx,_ in enumerate(prices):
        first = prices.pop(0)
        for j in prices:
        	answer[idx]+=1
            if first>j:
                break
    return answer

 

코드 리뷰 후 // deque 사용

def solution(prices):
    from collections import deque
    answer = [0]*len(prices)
    prices =deque(prices)
    for idx,_ in enumerate(list(prices)):
        first = prices.popleft()
        for j in prices:
            answer[idx]+=1
            if first>j:
                break
    return answer

 

깨달은 점

1. pop()은 O(1), pop(index)는 O(n) 시간이 걸린다. 이유는 해당 인덱스 값을 pop 하는 건 O(1)이지만 그 후 앞으로 다 땡겨줘야하기 때문에 O(n)이 걸린다고 한다.

2. 큐를 이용하여 문제를 풀고싶을 때는 collections의 deque를 이용하자. deque는 자료구조의 큐처럼 값을 앞, 뒤에서 꺼내고 넣을 수 있다.