[프로그래머스] 주식가격 - 파이썬/python

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

초 단위로 기록된 주식가격이 담긴 배열이 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지 구하는 문제다.

 

제한사항

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

 

예시

Example 1:

prices: [1, 2, 3, 2, 3]
return: [4, 3, 1, 1, 0]

 

풀이

스택을 활용하여 문제를 풀었다.

def solution(prices):
    answer = [0] * len(prices)
    stack = []
    
    for i in range(len(prices)):
        # 현재 가격이 마지막 가격보다 작을 때 -> 시간 기록
        while stack and prices[stack[-1]] > prices[i]:
            idx = stack.pop()
            answer[idx] = i - idx
              
        stack.append(i)
    
    # 스택에 남아있는 가격 -> 끝까지 유지된 경우
    for idx in stack:
        answer[idx] = len(prices) - idx - 1
    
    return answer

• 정답 리스트를 입력 리스트의 길이만큼 0으로 초기화하고, 스택을 빈 리스트로 생성한다.
• 각 가격의 인덱스를 순회하면서 가격이 떨어질 때 시간을 기록한다.
  • 현재 가격이 이전 가격보다 작을 때, 스택에서 인덱스를 꺼내고 시간 차이를 계산
• 반복문이 끝난 후 스택에 남아있는 인덱스는 가격이 떨어진 적 없는 경우로, 유지 시간을 계산한다.
  • 유지 시간 = 총 길이 - 인덱스 - 1