문제설명
n초 간의 주가를 초 단위로 기록한 배열 prices가 매개변수로 주어질 때, 각 초의 주가를 기준으로 해당 초 부터 n초 사이에 가격이 떨어지지 않은 시간은 몇 초인지 배열에 담아 return 하도록 solution 함수를 완성하세요.
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이 n은 2 이상 100,000 이하입니다. (2 <= n <= 100,000)
입출력 예
prices : [1, 2, 3, 2, 3]
return : [4, 3, 1, 1, 0]
1초의 주가는 1이며 1초부터 5초까지 총 4초간 주가를 유지했습니다.
2초의 주가는 2이며 2초부터 5초까지 총 3초간 주가를 유지했습니다.
3초의 주가는 3이며 4초의 주가는 2로 주가가 떨어졌지만 3초에서 4초가 되기 직전까지의 1초간 주가가 유지 된것으로 봅니다. 따라서 5초까지 총 1초간 주가를 유지했습니다.
4초의 주가는 2이며 4초부터 5초까지 총 1초간 주가를 유지했습니다.
5초의 주가는 3이며 5초 이후로는 데이터가 없으므로 총 0초간 주가를 유지했습니다.
풀이 00
큐 기반 풀이
- 주가를 유지한 시간(초) return
from collections import deque
def solution(prices):
answer = [0] * len(prices) # 결과를 저장할 리스트 초기화
queue = deque(enumerate(prices)) # (인덱스, 가격) 형태로 deque 생성
while queue:
idx, price = queue.popleft() # 현재 시간과 가격을 꺼냄
# 남아있는 큐를 순회하며 가격이 떨어지는 시점을 찾음
for future_idx, future_price in queue:
answer[idx] += 1 # 시간이 1초 증가
if price > future_price: # 가격이 떨어지면 종료
break
return answerprices에 담긴 값을 (인덱스, 가격) 형태로 deque를 생성한 후, queue가 빌때까지 남아있는 큐를 순회하며 가격이 떨어지는 시점을 찾고자 했다.
풀이 01
01. 최악의 경우, 시간복잡도 O(n^2)
def solution(prices):
n = len(prices)
answer = [0] * n
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
# 가격이 떨어지지 않은 기간 계산
answer[i] += 1
if prices[i] > prices[j]: # 가격이 떨어진 경우
break
return answer위 코드는 최악의 경우 시간복잡도가 O(n^2)이지만 실제로 가격이 일찍 떨어지는 경우, break로 최적화 된다. 따라서 최적화된 스택 기반의 풀이가 필요할 것이다.
02. 최적화된 스택 기반 풀이
위 풀이 00의 경우, 큐를 이용하여 문제를 풀었다. 하지만 문득 넣고 빼고를 고려해야 하는 문제가 아닌데 굳이 deque를 사용해야 했을까? 지속해서 deque를 사용한 문제 풀이를 사용하다보니 사고가 굳어져 버린 거 같기도 하다. 그렇다면 스택 기반의 풀이는 어떨까?
def solution(prices):
n = len(prices)
answer = [0] * n
stack = []
for i in range(n):
# 스택에 저장된 가격이 현재 가격보다 높으면 가격이 떨어진 것으로 처리
while stack and prices[stack[-1]] > prices[i]:
idx = stack.pop()
answer[idx] = i - idx # 가격이 유지된 기간 계산
stack.append(i)
# 스택에 남아있는 가격 처리 (끝까지 유지된 경우)
while stack:
idx = stack.pop()
answer[idx] = n - 1 - idx
return answer