초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
prices | return |
---|---|
[1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
def solution(prices):
answer = [0 for i in range(len(prices))]
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
answer[i] += 1
if prices[i] > prices[j]:
break
return answer
간단하게 생각해서 이중 for 문으로 해결하였다. 먼저 prices의 길이가 더 길어질 수 있으므로 리스트 컴프리헨션(list comprehension)으로 모든 값이 0 인 answer 리스트를 만들었다.(지금 생각하면 defaultlist로 만들어도 됐을 것 같다.) 그 후 가격이 하락하면 answer에 1을 더하는 것을 중지하는 형식으로 짰다.
정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.1MB)
테스트 2 〉 통과 (0.08ms, 10.2MB)
테스트 3 〉 통과 (1.15ms, 10.3MB)
테스트 4 〉 통과 (1.27ms, 10.2MB)
테스트 5 〉 통과 (1.49ms, 10.3MB)
테스트 6 〉 통과 (0.05ms, 10.2MB)
테스트 7 〉 통과 (0.74ms, 10.3MB)
테스트 8 〉 통과 (0.92ms, 10.3MB)
테스트 9 〉 통과 (0.05ms, 10.2MB)
테스트 10 〉 통과 (1.47ms, 10.2MB)
효율성 테스트
테스트 1 〉 통과 (145.75ms, 18.7MB)
테스트 2 〉 통과 (120.04ms, 17.7MB)
테스트 3 〉 통과 (191.83ms, 19.5MB)
테스트 4 〉 통과 (139.06ms, 18.3MB)
테스트 5 〉 통과 (92.72ms, 17.1MB)
채점 결과
정확성: 66.7
효율성: 33.3
합계: 100.0 / 100.0
사실 이 문제를 고민하면서 가장 많이 생각한 점이 O(n^2)이 되는 점이였다. 왠지 이중 for문을 돌리면 시간 초과가 될 줄 알았다. 하지만 다른 사람들도 이 부분을 고민해봤지만 해결하진 못한 것 같다.
from collections import deque
def solution(prices):
answer = []
prices = deque(prices)
while prices:
c = prices.popleft()
count = 0
for i in prices:
if c > i:
count += 1
break
count += 1
answer.append(count)
return answer
collections에서 deque를 가져와서 짠 코드로 while 문을 통해 prices 내의 값들을 가져와서 가격이 떨어지기 전까지 1씩 더하고 떨어지면 1을 더하고 for 문을 끝내는 형태이다.