내가 푼 풀이
def solution(prices):
answer = [0 for price in range(len(prices))]
time = []
time.append(0)
next = 1
while time:
if next < len(prices): # 리스트 크기 제한하기 위함
while time:
front = time[len(time) - 1]
if prices[front] > prices[next]: # 2. stack front와 next 값 비교
time.pop()
answer[front] = next - front
else:
break
time.append(next)
else: # price 다 돌았음
for i in time:
answer[i] = next - 1 - i #남아있는 값들 시간 계산
break
next += 1
return answer이 문제는 구현이 어려웠다기 보다는 시간을 stack으로 둔다는 아이디어를 떠올리기 쉽지 않았던 것 같다.
구현 방법
1. 제일 처음 인자를 stack에 넣는다.
2. stack front 값과 다음에 들어올 next 값을 비교한다.
- next 값이 front 미만일 경우:
가격이 떨어졌으므로, stack 내 next값보다 작은 값들을 찾아서 answer(가격이 떨어지지 않았던 시간)를 업데이트한다.
next의 순번(인덱스) - front의 순번(인덱스) 를 하면 몇 초간 가격이 떨어지지 않았는지 구할 수 있다. - next 값이 front 이상일 경우:
따로 시간 업데이트를 하지 않는다.
- stack에 next값을 넣는다.
