[프로그래머스, 파이썬] 주식가격

풀이

• 단순하게 접근해본 풀이와 스택을 활용한 풀이 두 가지 유형의 풀이 중 
• 첫 번째 풀이는 단순하게 접근한 풀이로
• li에는 현재 위치로 부터 앞으로 있을 거리에 대한 배열
• 이후 반복문을 활용하여 해당 값보다 작은 값이 있을 경우 카운팅한 것을 배열에 추가 후 탈출하여 해결
• 당연하지만 시간 복잡도가 상대적으로 올라갈 수 밖에 없으며, 다른 문제에선 이런 풀이는 통과되지 않을 듯하다.
• 그래서 두 번째 풀이로 스택으로 접근한 풀이인데
• 해당 풀이는 종종 나오는 것으로 이후의 값과 비교하려 할 경우
• stack이라는 배열에 값이 있을 경우 마지막 값과 비교한 후 
• 그에 따른 결과를 result에 적용하여 해결
• 다만 여기서 while문 또한 stack에 값이 있을 경우에 동작해야한다는 것을 기억하기.

 

첫 번째 풀이

def solution(prices):

    result = [i for i in range(len(prices)-1,-1,-1)]

    for i in range(len(prices)):

        cnt = 1

        for j in range(i+1,len(prices)):

            if prices[i] > prices[j]:

                result[i] = cnt

                break

            else: cnt += 1

    return result

 

두 번째 풀이

def solution(prices):

    result = [i for i in range(len(prices)-1,-1,-1)]

    stack = []

    for i,p in enumerate(prices):

        if stack:

            while stack and stack[-1][1] > p:

                idx,_ = stack.pop()

                result[idx] -= result[i]

        stack.append([i,p])

    return result