사용자 도구

사이트 도구


ps:problems:programmers:42584

주식가격

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42584
출처프로그래머스
문제 번호42584
문제명주식가격
레벨Level 2
분류

스택

시간복잡도O(n)
인풋사이즈n<=100,000
사용한 언어Python
해결날짜2021/05/21
태그

고득점 Kit - 스택/큐

풀이

  • 스택에는 아직 감소하지 않은 주식가격들을 저장하고 있는 것이 기본적인 풀이법. 이렇게 하면 증가하는 순서로 스택이 유지된다. 흔히 쓰이는 테크닉이다.
  • 시간 복잡도는 모든 원소를 한번씩 스택에 추가/삭제하므로 O(n)이 된다.
    • 그러나 다른 사람들의 풀이를 보면 O(nm)의 코드들도 많이 상위에 올라가 있다..

코드

"""Solution code for "Programmers 42584. 주식가격".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42584
- Solution link: http://www.teferi.net/ps/problems/programmers/42584
"""


def solution(prices):
    answer = [None] * len(prices)
    stack = []
    for cur_time, cur_price in enumerate(prices):
        while stack and prices[stack[-1]] > cur_price:
            time = stack.pop()
            answer[time] = cur_time - time
        stack.append(cur_time)
    for time in stack:
        answer[time] = cur_time - time
    return answer

토론

댓글을 입력하세요:
L V Q P᠎ M
 
ps/problems/programmers/42584.txt · 마지막으로 수정됨: 2021/05/21 07:11 저자 teferi