💻코딩테스트 문제풀이15

Chapter10. 동적 프로그래밍

[문제42] 도둑질 - Level4

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return하도록 solution 함수를 완성하세요.

[제한사항]

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

[문제풀이]

def solution(prices):
	size = len(prices)
    answer = [0] * size
    for i in range(size):
    	for j in range(i + 1, size):
        	if prices[i] <= prices[j]: answer[i] += 1
            else:
            	answer[i] += 1
                break
    return answer

[코드작성]

1. 주식 가격을 쌓아둘 스택과 상승세가 얼마나 오래 지속되었는지에 대해 기록을 남길 배열을 생성

def solution(prices):
	stack = []
    answer = [0] * len(prices)

2. 각 금액의 정보를 for문으로 순회하면서 상승세 여부를 확인

for i in range(len(prices)):
	while stack and prices[stack[-1]] > prices[i]:
    	past = stsack.pop()
        answer[past] = i - past
    stack.append(i)

3. 남은 스택을 전부 비우고, 정답을 반환

for i in stack:
	answer[i] = len(prices) - 1 - i
    
return answer

[전체코드]

def solution(prices):
	stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        while stack and prices[stack[-1]] > prices[i]:
            past = stsack.pop()
            answer[past] = i - past
        stack.append(i)
        
    for i in stack:
	answer[i] = len(prices) - 1 - i
    
return answer