처음에는 단순하게, 시간이라는 배열을 만들어서 가격들에게 각 시점마다 현재 시점의 가격과 비교해서 떨어지지 않을때마다 1초라는 값을 추가 해줬다. 추가로 한번 떨어진 것은 flag를 통해 다시 비교하지 않도록 만들었다.
def solution(prices):
answer = [0] * len(prices)
flag = [0] * len(prices)
for time, price in enumerate(prices):
if time == len(prices)-1:
break
for i in range(time+1):
if prices[i] <= prices[time] and flag[i] == 0:
answer[i] += 1
else:
flag[i] = 1
return answer
하지만 이 경우에는 만약 끝까지 가격이 떨어지지 않는 경우, 매번 전체 리스트를 돌면서 가격을 비교해야해서 시간이 오래걸린다. 그 결과로 효율성 테스트에서 떨어졌다.
이를 해결하기 위해서, 가격이 자신보다 낮은 가격을 만날때까지 리스트를 한번 도는 것으로 구현했다. 이렇게 하면, 뒤에 값들은 굳이 앞에 값들을 비교하지 않아 더 짧은 시간에 구현 가능하다.
def solution(prices):
answer = []
for i in range(len(prices)):
cnt = 0
for j in range(i, len(prices)-1):
if prices[i] > prices[j]:
break
else:
cnt += 1
answer.append(cnt)
return answer
'Study > Algorithm' 카테고리의 다른 글
[백준] 1655번 : 가운데를 말해요 (Python) (0) | 2021.12.06 |
---|---|
[프로그래머스] 가장 큰 수 (Python) (0) | 2021.12.05 |
[백준] 9663번 : N-Queen (Python) (0) | 2021.11.30 |
[백준] 5430번: AC (Python) (1) | 2021.11.29 |
[백준] 10828번: 스택 (Python) (0) | 2021.11.25 |