[프로그래머스][stack/queue] 주식가격 python (200722)

1. 문제 

 

 

1) 문제 설명

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

 

 

2) 제한사항 

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

 

3) 입출력 예시 

 

prices                               return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

 

4) 입출력 예시 설명 

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

2.풀이 

1) 이중 for 문을 이용한 간단한 풀이 (통과)

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

나만... 스택큐로 풀려고 했던건가....

당연히 이중 포문을 돌리면 런타임 에러가 뜰줄 알았는데 아니었다 (알다가도 모르겠는 프로그래머스)

하지만 이번 유형은 스택 큐 이니까 pop 을 활용한 다른 풀이들을 살펴봤다. 

 

 

2) 이중 반복문 활용  + deque (통과)

from collections import deque

def solution3(prices):
    answer = []
    prices = deque(prices)

    while prices: #prices 를 모두 탐색해서 [] 되면 stop
        c = prices.popleft() # prices 의 첫숫자를 기준점으로 잡고
        count = 0
        
        for i in prices:  # 나머지 숫자 하나씩 다 살펴보기
            if c > i: # 감소하는 경우라면
                count += 1 # count+=1 하고 중단
                break
            count += 1 # 아니면 count+=1 늘리며 계속 탐색

        answer.append(count)
    return answer

반복문 마다 출력값이 찍히는걸 확인해보면 아래와 같다. 

 

c 1   prices [2, 3, 2, 3]  answer [4]
c 2   prices [3, 2, 3]     answer [4, 3]
c 3   prices [2, 3]         answer [4, 3, 1]
c 2   prices [3]             answer [4, 3, 1, 1]
c 3   prices []               answer [4, 3, 1, 1, 0]

 

 

price 리스트에서 맨 앞의 값을 deque 를 활용해 빼낸뒤 (빼진 값은 c에 할당) 

나머지 리스트 요소들을 각각 비교하면서 count 하는 방식이다. 

위의 방법과 다를건 없지만, 큐스택 개념을 활용하는게 큰 차이일듯 

 

근데 왜 price list 를 deque 로 만들고, popleft() 과정을 번거롭게 거쳤을 까 싶었다. 

사실 리스트에 맨앞의 요소를 뽑는건 디큐로 안만들고 바로 pop(0) 을 해도 되는데.?

그 이유는 !!!!

 

 

3) 이중 반복문 활용  + 리스트 pop(0) 활용   (런타임에러)

 

오!!!! 런타임에러다!!!! 

def solution(prices):
    answer = []
    while prices:
        c = prices.pop(0)

        count = 0
        for i in prices:
            if c > i:
                count += 1
                break
            count += 1
        answer.append(count)
    return answer

 

그 이유는 list 의 pop(0) 은 시간 복잡도가 o(n) 인데

deque로 변환시킨 뒤 popleft() 는 시간 복잡도가 o(1) 이다! 속도면에서는 deque popleft()가 월등히 빠른 것 !

시간 복잡도를 생각하면, 앞으로 큐 문제는 리스트가 아닌 디큐로 풀어야한다! 

 

정리해보자면

유형	메소드	시간복잡도
스택 (First in Last out)	list.pop() #맨뒤에놈 뽑기	o(1)
	deque.pop()	o(1)
큐 (First in First out)	list.pop(0) #맨앞에놈 뽑기	o(n)
	deque.popleft()	o(1)

** 디큐는 스택과 큐를 합친 자료구조 형태로 가장자리에 원소를 넣거나 뺄 수 있음 

 

  " deque.popleft ()는 list.pop (0)보다 빠릅니다. deque.pop (0)은 O(n)을 사용하는 반면 deque는 대략 O (1)에서 popleft ()를 수행하도록 최적화 되었기 때문입니다. deque objects )를 참조하십시오. " 

 

+) deque 에 대한 자세한 설명은 아래의 링크를 따라 

 

https://ooeunz.tistory.com/31

[Python] Dequeue 사용하기

 

3. 정리 

큐 문제는 디큐로 풀어야 하는 것이었다. 

리스트 pop(0) 쓰는것 지양하기.