분류
스택／큐
문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력
| prices | return |
|---|---|
| [1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
| [1, 2, 3, 2, 3, 3, 1] | [6, 5, 1, 3, 2, 1, 0] |
문제 이해하기 위한 해설
- 다음 배열의 전체 시간 중에 가격이 내려가있는 시간을 구하는 게 아니라 떨어지기까지의 시간을 구하는 것
- 입출력 예2에 대해서,
- 1 : 2, 3, 2, 3, 3, 1 -> 6초간 떨어지지 않으니 결과값 6
- 2 : 3, 2, 3, 3, 1 -> 5초간 떨어지지 않으니 결과값 5
- 3 : 2 -> 1초 뒤에 떨어지니 기대값 1
- 2 : ~~ 결과값 3
- 3 : ~~ 결과값 2
- 3 : ~~ 결과값 1
- 1 : 결과값 0
아이디어
-
스택/큐 문제라는 거를 알고 있어서, 큐로 접근하려고 했음
-
(인덱스, 가격) 튜플을 원소로 하는 덱을 선언하고, 각 원소에 대해서
-
현재 가격보다 작지 않은 가격들은 pop 해서 tmp 덱에 추가해두고, 현재 가격보다 작은 가격을 만나면 tmp 덱의 길이에 따라 answer가 정해지도록 구현하고 있었는데
-
이렇게 하면 예외처리할 게 좀 많아지고 괜히 복잡해지는 것 같아서 단순하게 가보기로 함
내 코드
from collections import deque
def solution(prices):
deq = deque(prices)
answer = []
while deq:
now = deq.popleft()
sec = 0
for p in deq: # 나머지 원소에 대해서
sec += 1
if now > p: # 가격이 떨어지면 break
break
answer.append(sec)
return answer-
효율성 따지다가 문제를 못 풀겠어서 우선 단순하게 현재 pop한 값에 대해서 덱에 남아있는 값들을 순회하면서 값을 비교하는 걸로 구현
-
애초에 덱이 아니더라도 그냥 이중 for문으로도 풀리는 건데 더 좋은 코드를 검색해서 찾았다
다른 사람 코드
# prices = [1, 2, 3, 2, 3, 1] return [5, 4, 1, 2, 1, 0]
def solution(prices):
length = len(prices)
# answer을 max값으로 초기화
answer = [ i for i in range (length - 1, -1, -1)]
# 주식 가격이 떨어질 경우 찾기
stack = [0]
for i in range (1, length):
while stack and prices[stack[-1]] > prices[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answerdef solution(prices):
# answer = 몇초 후 가격이 떨어지는지 저장하는 배열
answer = [len(prices)-i-1 for i in range(len(prices))]
# stack = prices의 인덱스를 차례로 담아두는 배열
stack = [0]
for i in range(1, len(prices)):
while stack:
index = stack[-1]
# 주식 가격이 떨어졌다면
if prices[index] > prices[i]:
answer[index] = i - index
stack.pop()
# 떨어지지 않았다면 다음 시점으로 넘어감 (주식 가격이 계속 증가하고 있다는 말)
else:
break
# 스택에 추가한다.
# 다음 시점으로 넘어갔을 때 다시 비교 대상이 될 예정이다.
stack.append(i)
return answer- 설명 내일 추가해야지 ...
Source
