[프로그래머스] 주식가격 (Python)

💁🏻 나의 풀이

def solution(prices):
    answer = [0] * len(prices)
    stack = []

    for i in range(len(prices)):
        while stack and prices[i] < prices[stack[-1]]:
            top = stack.pop()
            answer[top] = i - top

        stack.append(i)

    while stack:
        top = stack.pop()
        answer[top] = len(prices) - 1 - top

    return answer

• 스택을 이용해서 위치를 매번 쌓다가 가격이 떨어지는 시점에 스택에 가격이 떨어진 위치가 있는지 비교
• for문이 끝나고도 stack에 남은 위치들은 모두 가격이 떨어지지 않은 것들임
• LeetCode의 Trapping Rain Water 문제와 비슷하게 풀면 되겠다고 느낌

👀 다른 사람 풀이

🔗 https://velog.io/@soo5717/프로그래머스-주식가격-Python

from collections import deque

def solution(prices):
    queue = deque(prices)
    answer = []

    while queue:
        price = queue.popleft()
        sec = 0
        for q in queue:
            sec += 1
            if price > q:
                break 
        answer.append(sec)        
    return answer

# prices = [1, 2, 3, 2, 3, 1] return [5, 4, 1, 2, 1, 0]
def solution(prices):
    length = len(prices)

    # answer을 max값으로 초기화  
    answer = [ i for i in range (length - 1, -1, -1)]

    # 주식 가격이 떨어질 경우 찾기
    stack = [0]
    for i in range (1, length):
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

• 첫 번째 솔루션은 모든 위치에 대해 가격이 떨어지는 가장 가까운 위치를 찾는 방식임 (큐 사용)
• 두 번째 솔루션은 본인의 솔루션과 로직은 완벽히 동일
• 다만, 본인와 달리 answer 의 초기화를 미리 함으로서 마지막에 스택에 남은 위치들을 처리할 필요를 없앤 부분이 좋아 보임