[Programmers] 주식가격 바로가기
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
prices | return |
---|---|
[1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
answer
의 초기 상태는 주식가격(prices
)이 오름차순으로 정렬되었을 때의 상태와 같도록 저장한다.prices
가 [1, 2, 4, 2, 3, 4]
라면 answer
의 초기 상태는 [5, 4, 3, 2, 1, 0]
이다.stack
은 주식 가격의 변동 상태를 누적으로 저장한다.prices
의 값이 [1, 2, 3, 2, 3]
인 경우의 상황answer = [4, 3, 2, 1, 0]
i = 1
인경우stack = [0]
while stack and prices[stack[-1]] > prices[i]
prices[0] > prices[i]
가 성립하지 않는다.stack
에 1
추가i = 2
인경우stack = [0, 1]
while stack and prices[stack[-1]] > prices[i]
prices[0] > prices[i]
가 성립하지 않는다.stack
에 2
추가i = 3
인경우stack = [0, 1, 2]
while stack and prices[stack[-1]] > prices[i]
j = 2, stack = [0, 1]
answer[2] = 3 - 2
answer = [4, 3, 1, 1, 0]
prices[0] > prices[i]
가 성립하지 않는다.stack
에 3
추가i = 4
인경우stack = [0, 1]
while stack and prices[stack[-1]] > prices[i]
prices[0] > prices[i]
가 성립하지 않는다.stack
에 4
추가answer = [4, 3, 1, 1, 0]
의 값을 반환한다.✍ 코드
def solution(prices):
N = len(prices)
answer = [ i for i in range (N - 1, -1, -1)]
stack = [0]
for i in range (1, N):
while stack and prices[stack[-1]] > prices[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer