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

문제

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어진다.
가격이 떨어지지 않은 기간은 몇 초인지를 return

prices				return
[1, 2, 3, 2, 3]		[4, 3, 1, 1, 0]

---

내 풀이

조건 정리

1) 현재 인덱스의 값이 그 다음의 값들 보다 작거나 같으면 인덱스를 지날 때마다 +1이 된다.
2) 마지막 인덱스의 값은 비교 대상이 없으므로 무조건 0이다.

풀이

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

• 직관적이지만 이중 for문과 그 안에 if문 까지 쓰게 되어 효율성이 매우 떨어짐
• 문제는 풀 수 있는 풀이이지만 문제의 의도를 파악하지 못함

---

다른 풀이

deque

• 데크(deque)의 개념
  보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다.

• 특징
  - 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.
  - 데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.
  - 컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.

출처: https://leonkong.cc/posts/python-deque.html

해석

이 문제는 여러가지 방법으로 풀 수 있지만 가져온 풀이에서는 deque라는 메서드(stack + que)를 사용하여 문제를 해결하였다.

풀이

from collections import deque

def solution(prices):
    answer = []
    prices = deque(prices)
    
    while prices:
        sec = 0
        p = prices.popleft()
        
        for price in prices:
            sec += 1
            if price < p:
                break
                
        answer.append(sec)
    
    return answer

answer = []
prices = deque(prices) 

> prices를 deque로 변환

---------------------------

while prices:
        sec = 0
        p = prices.popleft()
        
> while prices: popleft()는 deque의 가장 첫 번째 값을 pop하는 것이다.
  이를 계속할 경우 prices 내 모든 값이 없어질 것이고 그러면 while이 끝난다.
> p = prices.popleft() : 인덱스가 가장 작은 값을 pop하여 가져온 값이다.

---------------------------

for price in prices:
            sec += 1
            if price < p:
                break
                
        answer.append(sec)

> for price in prices: prices는 popleft 하고 난 뒤의 deque이다.
> sec += 1
  if price < p: popleft한 값이 price보다 크면 break 아니면 sec += 1
  	break