[프로그래머스] 주식 가격 level2 - python

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

프로그래머스

 

 

 

문제 설명

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

 

 

 

 

 

 

 

 

제한사항

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

 

 

 

 

 

 

 

 

입출력 예

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

 

 

 

 

---

이 문제는 가격이 주어졌을 때 해당 가격으로부터 몇 초 후에 가격이 떨어지는 지를 return 해야 한다.

 

입출력 예를 보면 prices가 [1, 2, 3, 2, 3] 로 주어져있다. 이 중 1을 기준으로 보면 후에 가격이 더이상 하락하지 않기 때문에 4가 return된다. 하지만 3의 경우 바로 가격이 2로 하락되기 때문에 1이 return된다. 

 

 

 

 

 

 

 

 

Queue 사용

from collections import deque

def solution(prices):
    answer = []
    queue = deque(prices)
    while queue:
        num = queue.popleft()
        count = 0
        for target in queue:
            if num <= target:
                count += 1
            else:
                count += 1
                break
        answer.append(count)
    return answer

먼저 리스트 1개와 count변수를 0으로 초기화 한다. 그리고 prices는 deque로 받은 후 가격을 1개씩 가져와 나머지 가격을 차례대로 비교하여 가격이 하락할 때까지 count 변수에 1씩 더하며, 가격이 하락하는 순간 for문을 종료한다. 

 

처음에는 deque를 사용하지 않고 리스트를 사용하였다. 하지만 리스트를 사용하면 시간 초과가 되었고 이를 해결하기 위해 보다 시간 복잡도 측면에서 효율이 좋은 deque를 사용하였고 시간 초과가 되는 문제를 해결되었다.