프로그래머스 - 주식가격 (Python)

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

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

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

 

 

# 풀이 1 : deque

def solution(prices):
    from collections import deque
    queue=deque(prices)
    result=[]
    
    while queue:
        now=queue.popleft()
        cnt=0
        for i in queue:
            if now<=i:
                cnt+=1
            else:
                cnt+=1
                break
        result.append(cnt)
    
    return result

 

# 풀이 2 : 이중 포문

def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices) - 1):
        for j in range(i + 1, len(prices)):
            answer[i] += 1
            if prices[i] > prices[j]: 
            break

    return answer

 

 

밑에는 제가 시도했던 방법들과 새로 알게된 deque 객체

 

# 시도 1

로직 : pop(0)을 써서 현재 인덱스 이전을 제외하고 다음 요소들과 비교하도록 구현하였다. 지금 생각해보면 왜 굳이 이랬지 싶다. pop 안쓰고 for i, j 해서 탐색해도 나올 텐데.. 저번 포스팅에서 본 pop(0)에 꽃혔나보다.

def solution(prices):
    
    temp = [0] * len(prices)
    i = 0
    for price in prices[:]:
        now = prices.pop(0)
        for x in prices:
            if now <= x:
                temp[i] += 1
            else: 
                temp[i] = 1
                break
        i = i + 1
        
    return temp

결과 : 테스트 케이스 1은 성공 but 전체 테스트 케이스는 런타임 에러 ^^ 

구글링해보니 나처럼 pop()을 써서 런타임 에러가 뜬 사람들을 볼 수 있었다. ㅠ

(염탐한 링크 : huidea.tistory.com/19,  ooeunz.tistory.com/31 )

 

런타임 에러가 났던 이유는?

list pop(0) 의 시간 복잡도 = o(n) // 이야 o(n)으로도 런타임 에러가 날수 있었군요~

deque의 popleft()는 시간 복잡도가 o(1) 이라고 하네요.

더 빠르니까 앞으로 이거 애용하는 걸로~ 걍 이중포문 i, j로 비교해버릴라 아오

 

deque 객체

deque는 스택과 큐를 합친 자료구조이다. 가장자리에 원소를 넣거나 뺄 수 있다.

 

스택과 달리 큐를 list로 이용하지 않는 이유

 스택에서 list.append와 list.pop()을 이용했던 것처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다.

 하지만 pop()의 time complexity는 O(1)인 반면 pop(0)의 time complexity는 O(N)이기 때문에 시간이 오래 걸린다. 따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.

 

deque 사용법

사용법은 list랑 비슷하네요. 큐로 사용할때 left로 빼는 메소드가 있나보군

from collections import deque

==========================================================================

# 빈 큐 만들기
deque1 = deque()

# 원소가 있는 큐 만들기
deque2 = deque([1, 2, 3])

# 큐 최대 길이 명시하기(원소를 이보다 많이 넣으면 maxlen이 자동 갱신됨)
deque3 = deque(maxlen=5)

==========================================================================

# 원소 추가하기
my_deque = deque()
my_deque.append(3)
print(my_deque)

==========================================================================

# 원소 제거하기
my_deque = deque([1,2,3])
while my_deque:
    print("{}을/를 pop했습니다".format(my_deque.popleft()))

# 1을/를 pop했습니다
# 2을/를 pop했습니다
# 3을/를 pop했습니다

==========================================================================

# 모든 원소 지우기
my_deque = deque([1,2,3])
print("전:", my_deque)
my_deque.clear()
print("후:", my_deque)

# 전: deque([1, 2, 3])
# 후: deque([])

==========================================================================

# 원소 수 알아내기
my_deque = deque([1,2,3], maxlen=5)
print(len(my_deque))

# 3

 

이렇게 바꿔 봤는데 똑같이 런타임 에러나옴ㅠ  copy가 o(n)이라서..? 

from collections import deque
import copy
def solution(prices):
    
    dq = deque(prices)
    temp = [0] * len(prices)
    i = 0
    for price in copy.deepcopy(dq) :
        now = dq.popleft()
        
        for x in dq:
            if now <= x:
                temp[i] += 1
            else: 
                temp[i] = 1
                break
        i = i + 1
        
    return temp

 

 

+ 놀라운 사실~ list에서 pop()을 하면 모든 원소를 돌지 않습니다.

 

ex 1. 원소 1 다음에 2로 넘어가지 않고, 3으로 for문이 돌아간다.

원인 : remove시 원본 리스트 데이터도 훼손되기 때문에 발생한다.

def solution(prices):
    answer = []
    temp = [0] * len(prices)
    i = 0
    for price in prices[:]:
        print("바깥 포문")
        print(price, prices)
        now = prices.pop(0)
        print("-->", price, prices)
    return temp

 

ex 2. [:] 로 해결! 

def solution(prices):
    answer = []
    temp = [0] * len(prices)
    i = 0
    for price in prices:
        print("바깥 포문")
        print(price, prices)
        now = prices.pop(0)
        print("-->", price, prices)
    return temp

 

(참고 : devpouch.tistory.com/110 )

[python] list로 for문 돌면서 remove할때 주의할점