나의 풀이
def solution(prices):
answer = [0] * len(prices)
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- 큐, 스택 없는 제일 단순한 접근이다.
- 다음 인덱스에 가격이 낮아진다면 종료가된다. 아니면 1초씩 계속 더해준다.
큐를 사용한 풀이
from collections import *
def solution(prices):
queue = deque(prices)
answer = []
while queue:
price = queue.popleft()
sec = 0
for s in queue:
sec += 1
if price > s:
break
answer.append(sec)
return answer- 큐를 사용하여 큐에 원소가 존재하는동안 반복을 한다. 큐에서 제일 첫 번째 요소를 꺼내어 price 변수에 담아둔다.
- 첫 번째 요소를 제외한 큐를 돌면서 마찬가지로 price보다 낮은 가격이 있으면 반복을 종료하고, 아니면 계속 sec += 1을 해준다.
- for문을 빠져나와 answer에 sec을 넣어준다.
- 결과적으로 접근 방식은 같기 때문에 성능 차이가 별로 없을 줄 알았는데 효율성 테스트에서 2배 정도 차이가 났다.
스택을 사용한 풀이
def solution(prices):
stack = []
answer = [i for i in range(len(prices) - 1, -1, -1)]
for i in range(len(prices)):
while stack and prices[stack[-1]] > prices[i]:
sec = i - stack[-1]
answer[stack.pop()] = sec
stack.append(i)
return answer- 백준의 17298번 오큰수 문제와 매우 유사하다.
- 주식가격이 떨어지지 않는다면 answer는 총 원소의 개수가 3개라면 2, 1, 0 과 같은 형태로 나올 것이다. 그렇기 때문에 일단 문제가 없다고 가정하고 answer를 세팅해준다.
- 그리고 스택을 돌리면서 prices에서 stack의 마지막 원소번째의 가격보다 prices[i]의 가격이 더 낮다면 가격이 떨어졌다는 의미이므로 서로의 인덱스 차이를 구해주고, answer의 stack.pop()번째 인덱스에 해당 값을 입력해준다.
- 스택이 비어있거나 다음 가격이 더 크거나 같은 경우에는 스택에 인덱스를 넣어준다.
- 효율성 측면에서는 스택이 가장 빨랐다.
