[스택/큐] 주식 가격 (프로그래머스, Level2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42584

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

제한사항 & 입출력 예

코드

정답

본 코드가 정답처리되긴 했는데, 스택/큐 단원에 맞게 스택/큐를 활용해서 풀지 않았다. (다른 구현 방법을 더 생각해볼 것이다.)

💡 아이디어 (구현 방식)

• prices 배열에 마지막 요소로 0을 추가해줬다. (prices의 각 가격은 1 이상 10,000 이하이기 때문에 0은 주어진 prices 배열의 모든 가격보다 작은 값이 다람쥐🐿)
• 마지막에 0을 추가해줬기 때문에, 끝까지 감소하지 않는 가격들도 k 값을 구할 수 있다.

def solution(prices):
    answer = []
    
    prices.append(0)
    for i in range(len(prices)):
        now = prices[i]
        for j in range(i+1, len(prices)):
            if prices[j] < now:
                if j == len(prices) - 1:
                    answer.append(j-i-1)
                    break
                else:
                    answer.append(j-i)
                    break
    
    return answer

실행 결과

• 입력된 테스트 케이스들을 모두 통과하긴 했지만 효율성 테스트 부분에서 더욱 개선해야할 필요성이 느껴진다. 시간을 더 단축시킬 수 있는 다른 방법도 생각해봐야겠다 😊

시간 초과

• prices 배열의 0번째 값을 계속해서 pop 하면서, 남은 값들 중 작은 값을 만나기 전까지의 개수를 구해서 answer 배열에 추가하는 방식이다.

def solution(prices):
    answer = []
    
    stack = []
    while len(prices) > 0:
        stack.append(prices.pop(0))
        k = 0
        for i in prices:
            if i >= stack[-1]:
                k += 1
            elif i < stack[-1]:
                k += 1
                break
        answer.append(k)
    return answer

실행 결과