https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=python3
문제
문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
| prices | return |
|---|---|
| [1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
입출력 예 설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
풀이
주식 그래프는 연속적을로 나타난다. 문제에서 어떤 시점의 가격이 저점으로 유지되는 기간을 물어보았다.
어느 한 지점에서 관심이 있는 부분은 빨간 부분이다. 현재 가격보다 낮을 때는 관심 대상이 아니다. 그리고 현재 가격보다 높지만 이미 낮은 구간을 지났다면 낮은 구간에서 이미 처리 (답이 나옴) 되었을 것이다.
빨간부분은 끝에서 뒤로 하나씩 보면서 현재 가격보다 높으면 답이 나오고, 같아지면 더이상 볼 필요가 없어진다. (위의 이유 때문에) 따라서 마지막부터 하나씩 보며 값이 같아지면 멈추면 된다. 이미 쌓아진 값들을 순서대로 보기때문에 stack을 사용할 수 있다.
prices의 값들을 순회하며 stack에 넣기 전에 이전의 stack을 뒤에서부터 확인하며 기간을 계산하고 stack에서 제거한다.
그럼 stack에는 노란부분만 남게될 것이다. 그리고 가격이 더 떨어진다면 실선화살표를 기준으로 확인하며 이보다 노란선 가장 뒤부터 화살표와 가격이 같아지는 부분까지 확인한다.
마지막까지 처리되지 않은 값들이 stack에 남아있을 것이며 이들은 price의 길이-1를 이용해서 유지된 기간을 계산한다.
코드
def solution(prices):
answer = [0] * len(prices)
stack = []
for idx, price in enumerate(prices):
while stack:
if stack[-1][1] > price:
node = stack.pop()
answer[node[0]] = idx - node[0]
else:
break
stack.append((idx, price))
for node in stack:
answer[node[0]] = len(prices) - 1 - node[0]
return answer