스택/큐 주식가격

프로그래머스 코딩테스트 고득점 Kit 주식가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 1가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

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

풀이 포인트

• 스택을 응용한다.
• 출처 : deftkang의 IT 블로그- [알고리즘]주식가격(프로그래머스 문제) python 풀이(스택)

solution.py

python3

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

    for i, p in enumerate(prices):
        while stack and p < 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

처음에 구현한 방법

• 정확성 테스트는 통과되나 효율성 테스트를 통과하지 못한다.

python3

def solution(prices):
    answer = []
    while prices:
        price = prices.pop(0)
        if any(price > i for i in prices):
            for i, p in enumerate(prices):
                if p < price:
                    answer.append(i + 1)
                    break
        else:
            answer.append(len(prices))
    return answer