프로그래머스 LV2 - 주식 가격

문제 링크

내 풀이

def solution(prices):
    times = []
    for i, price in enumerate(prices):
        time = 0
        for idx in range(i+1, len(prices)):
            if prices[idx] >= price:
                time += 1
            else:
                time += 1
                break
        times.append(time)
    return times      

다른 풀이

def solution(prices):
    n = len(prices)
    answer = [0] * n # 가격이 떨어지지 않은 기간을 저장할 배열

    # 스택을 사용해 이전 가격과 현재 가격 비교
    stack = [0] # 스택 초기화
    for i in range(1,n):
        while stack and prices[i] < prices[stack[-1]]:
            # 가격이 떨어졌으므로 이전 가격의 기간 계산
            j = stack.pop()
            answer[j] = i-j
        stack.append(i)
    
    while stack:
        j = stack.pop()
        answer[j] = n-1-j

    return answer

풀이 해석

• 가격이 떨어지지않으면 계속 stack에 쌓아준다
• 가격이 떨어지면 stack의 가장최근 index와 현재 떨어진 가격의 index의 차이를 구하고 이를 answer에 기록한다
• stack이 빌때까지 남은 stack원소를 이용해 answer값을 채운다