알고리즘 개요
- 초 단위로 기록된 주식가격이 담긴 배열 prices
- 가격이 떨어지지 않은 기간은 몇 초인지를 배열로 리턴
예시
- prices: [1, 2, 3, 2, 3]
- 1초 시점의 1원은 4초간 1원 밑으로 떨어지지 않음
- 2초 시점의 2원은 3초간 2원 아래로 떨어지지 않음
- 3초 시점의 3원은 다음 초에 2원으로 떨어졌으므로 1초 간 가격을 유지함
- 4초 시점의 2원은 다음 초에 3원이므로 1초 간 가격을 유지함
- 5초 시점의 3원은 다음 초 가격을 알 수 없으므로 0초 간 가격을 유지한 것으로 정의
- 결과 값: [4, 3, 1, 1, 0]
첫 번째 풀이
def solution(prices):
time = []
while prices:
second = 0
for i in range(1, len(prices)):
second += 1
if prices[0] > prices[i]:
break
prices.pop(0)
time.append(second)
return time
- 풀이법은 맞았지만
pop(0) 탓에 시간 복잡도가 올라가 효율성 테스트에서 시간 초과
- prices에 값이 있을 동안만 while문 for을 실행한다.
- for문에 들어간 순간
second += 1을 통해 시간을 측정한다.
- prices의 첫 번째 값이 prices[i]의 값보다 큰 경우 break를 통해 for을 멈춘 뒤, prices[0]을 없앤다.
- 측정된 시간 second는 time에 append된다.
- 이 과정을 반복한 뒤, prices의 값이 더 이상 없는 경우 time을 리턴한다.
통과된 풀이
def solution(prices):
time = []
idx = 0
while idx < len(prices):
second = 0
for i in range(idx, len(prices) - 1):
second += 1
if prices[i + 1] < prices[idx]:
break
idx += 1
time.append(second)
return time
- 통과된 풀이 또한 첫 번째 풀이와 기본 포맷을 같지만 단지 pop(0)을 사용하지 않고, 비교하는 현재 값의 인덱스를 idx 변수로 계속적으로 바꾸는 방식이다.
- while 문의 조건은 idx가 prices의 마지막 값 인덱스일 수 있도록 만들었다.
- for 문 또한 range의 첫 번째 값을 비교하고자 하는 값의 인덱스부터 시작되도록 설정한다.
- 이후에는 첫 번째 풀이와 같다. 만약 현재 값이 다음의 값보다 크면 for 문의 break한다.
- 그 뒤, price을 줄이지 않고(첫 번째 풀이) idx += 1을 사용하여 다음 비교 값의 인덱스를 변경하고, 측정한 시간(second)를 time에 추가한다.
