문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
| prices | return |
|---|---|
| [1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
코드
from collections import deque
def solution(prices):
answer = list()
# prices를 deque로 만들어주어서 왼쪽부터 데이터를 뽑아낼 수 있도록 만들어준다
prices = deque(prices)
# 계속해서 popleft를 사용해서 데이터를 추출할 것이기 때문에 만약에 queue가 비었다면 break 할 수 있도록 설정
while prices:
# 현재 값을 popleft로 받아오고 time = 0 으로 설정
current, time = prices.popleft(), 0
# popleft를 한 뒤 남은 가격들과 비교를 해서 만약 현재 가격이 더 작다면 time을 더해주고 만약에 현재 가격이 더 커지는 순간이 온다면 break를 한다.
for num in prices:
time += 1
if current > num:
break
answer.append(time)
return answer배운 점
처음에는 enumerate(prices)를 사용해서 빈 stack에 value를 하나씩 append 한 다음 stack의 길이 -1만큼의 index range 안에서 값 비교를 하여 가격이 떨어진 index를 answer 리스트에 입력해두었다. 그 다음에 또 다시 for문을 돌면서 index를 계산해주는 방식으로 진행했다. 첫 for문에서 stack에 하나씩 넣어주고 또 다시 그 stack을 반복문으로 돌리다 보니 정확도는 100퍼센트인데 시간 복잡도가 O(n^2)으로 효율성 테스트에서 0점(ㅋㅋ)을 받았다.
그렇다면 현재 내가 해야할 일이 prices에서 원소를 왼쪽부터 꺼내서 prices안의 원소들과 비교하는 것 인데 이를 어떻게 효율적으로 할 수 있을까 고민하다가 (코드를 많이 참고해서) deque를 활용하는 방식을 알아냈다. 왼쪽부터 데이터 추출이 가능한 deque를 활용하여 원소를 추출 후 for문을 사용하여 비교하다가 현재 값이 더 커지면 break하는 방식을 사용하면 시간 복잡도 O(n)으로 문제를 효율적으로 풀 수 있다.
