문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
Deque를 이용합니다.
Deque(Double-ended queue): 양쪽 끝에서 데이터의 삽입과 삭제가 가능한 자료구조
*deque는 스택과 큐의 기능을 모두 갖고 있으며, 많은 양의 데이터를 저장할 때 메모리를 효율적으로 사용할 수 있습니다.
주식 가격이 떨어지지 않는 기간을 계산하는 방식입니다.
from collections import deque
def solution(prices):
result = []
prices = deque(prices)
while prices:
time = 0
p = prices.popleft()
for i in range(len(prices)):
if p > prices[i]:
time += 1
break
time += 1
result.append(time)
return result
테스트 케이스는 모두 통과했으나 효울성 테스트에서 시간 초과로 문제를 해결하지 못했습니다.
위 코드의 시간 복잡도는 O(n^2) 입니다.
for 루프에서 len(prices)
를 사용했기 때문에 매번 prices의 길이를 구해야됩니다. 또한, 반복문을 돌며 prices[i]를 찾는 부분도 시간 초과에 한 몫 한 것 같습니다.
range가 아닌 리스트 반복문으로 변경했습니다.
from collections import deque
def solution(prices):
result = []
prices = deque(prices)
while prices:
time = 0
p = prices.popleft()
for i in prices:
time += 1
if p > i:
break
result.append(time)
return result