[Python3]프로그래머스_주식가격

문제출처:https://programmers.co.kr/learn/courses/30/lessons/42584?language=python3

접근법

문제길이가 매우 짧고 명료했다.
처음에 보고 이중 for문을 활용하여 단순하게 풀 수 있지 않을까 생각했는데
prices 배열 크기가 늘어날 시 시간초과에 걸릴까 하여 다른 방식으로 접근했다.

내 풀이의 핵심은 스택의 top만 확인하는 것이다.
0 ~ len(prices)-1 의 범위를 돌며
1. 스택의 top보다 작을 시 가격이 떨어진 시간을 계산하여 answer 배열에 추가하고 스택에서 빼준다.( while 문을 통해 스택의 top이 빼준 뒤에도 현재 인덱스의 가격보다 적다면 반복한다. )
2. 스택의 top보다 같거나 클 시 스택에 추가한다. 이는 스택에 추가된 모든 숫자들은 bottom ~ top 까지의 오름차순 정렬을 보장하여 1번 알고리즘의 계산이 가능하게 된다.

코드

def solution(prices):
    answer = []
    answer = [ 0 for i in range(len(prices)) ]
    s = []
    for i,price in enumerate(prices):
        if( not s ):
            s.append( (i,price) )
        else:
            while( s and s[-1][1] > price ):
                answer[s[-1][0]] = i - s[-1][0]
                s.pop(-1)
            s.append( (i,price) )
    while( s ):
        answer[s[-1][0]] = len(prices)-1 - s[-1][0]
        s.pop(-1)
    return answer