문제 링크 : programmers.co.kr/learn/courses/30/lessons/42584
prices의 길이를 n이라고 하면, 최대 O(nlogn)의 풀이가 가능해 보였다.
스택을 이용해서 문제의 요구사항대로 구현하고자 했다.
스택의 top에 있는 주식의 price가 추가하려고하는 주식의 price보다 같거나 작으면 그냥 스택에 push하고, 크면 스택 top 주식의 price가 추가하려고하는 주식의 price보다 같거나 작아질 때까지 pop을 한다.
따라서 스택을 이용한 풀이의 최종 시간 복잡도가 O(n)가 된다.
def solution(prices): # prices의 길이 : 1 <= n <= 100000 # 최대 O(nlogn) 정도 가능 n_prices = len(prices) answer = [0 for _ in range(n_prices)] stack = [(prices[0], 0)] # (주식 가격, stack에 push된 시점) for i, price in enumerate(prices): top_price = stack[-1][0] if top_price > price: # top_price <= price가 될 때까지 pop한 후에 push while top_price > price: stack_top = stack.pop() answer[stack_top[1]] = i - stack_top[1] if len(stack) == 0: break top_price = stack[-1][0] stack.append((price, i)) while len(stack) > 0: stack_top = stack.pop() answer[stack_top[1]] = n_prices - 1 - stack_top[1] # 최종 복잡도 : O(n) return answer
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 더 맵게 (0) | 2021.04.16 |
---|---|
[프로그래머스] 기능개발 (0) | 2021.04.14 |
[프로그래머스] 위장 (0) | 2021.03.27 |
[프로그래머스] 전화번호 목록 (0) | 2021.03.26 |
[프로그래머스] - 완주하지 못한 선수 (0) | 2021.03.20 |