문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

접근 방법

스택을 사용하였다. 스택에 prices의 원소들의 인덱스를 하나씩 넣고 스택의 가장 뒤에 있는 원소와 현재의 원소를 비교하여 현재 원소가 더 작을 경우 가격이 떨어진 것이므로 answer[스택의 가장 뒤에 있는 원소]를 현재 인덱스 - 스택의 가장 뒤에 있는 원소로 저장하고 스택을 pop시킨다. 이렇게 prices를 한번 순회하고 나면 stack에 원소들이 남는다. answer에 0으로 남아있는 원소들은 가격이 한번도 떨어지지 않은 경우이므로 스택의 가장 마지막에 존재하는 원소 - 현재 인덱스를 answer[현재 인덱스]로 저장한다.

• 정답을 저장할 배열 answer를 0 prices의 길이개로 채워준다.
• 스택으로 사용할 배열 stack을 선언한다.
• enumerate를 이용하여 prices를 순회하는 i, cur에 대한 for문을 돌린다.
  -> stack이 원소를 가지고 있고 cur이 prices[stack[-1]]보다 작을 경우 반복하는 while문을 돌린다.
  --> 임시 변수 last에 stack.pop()을 저장한다.
  --> answer[last]를 i-last로 갱신한다.
  -> stack에 i를 넣어준다.
• answer의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  -> 만약 answer[i]가 0이라면 answer[i]를 stack[-1]-i로 갱신한다.
• answer를 반환한다.

solution.py

def solution(prices):
    answer = [0]*len(prices)
    stack=[]
    for i, cur in enumerate(prices):
        while stack and cur<prices[stack[-1]]:
            last=stack.pop()
            answer[last]=i-last
        stack.append(i)
    for i in range(len(answer)):
        if answer[i]==0:
            answer[i]=stack[-1]-i
    return answer