https://programmers.co.kr/learn/courses/30/lessons/42584
(인덱스, 현재가)
의 튜플이 들어간다.현재가 < stack top의 price
라면 스택에 현재 가격을 push한다인덱스 - stack top의 인덱스
(그러니까 주식 가격이 떨어지지 않은 시간)을 answer
에 기록한다아 정말 알고리즘이란 할수록 느는게 맞구나 라고 생각하면서 당당하게 채점을 했는데 테케 1번만 빼고 전부 틀렸다.
당연히 내 로직은 틀리지 않았다는 자만심으로 코드를 훓어보다 문득 스치는 생각이...
왜 스택의 top만 pop하는거지...?
예를 들어 prices = [1, 2, 3, 2, 3, 1]
이라면, 두번째로 1을 만날 때에 (그러니까 idx==5
) 모든 2와 3에 대해서 시간이 기록되어야 한다. (하락이 시작되었으므로) 그러나 나의 코드에서는 맨 위의값만 단 한번 pop 하기 때문에 당연히 틀린 논리로 코드를 작성했고, 운좋게 테케만 맞았던 것 뿐이다.
그래서 처음에 생각한 해결법의 3번을 다음과 같이 수정하였다.
- 그 반대의 경우라면
현재가 >= stack top의 price
가 될 때 까지 stack을 pop한다. 매번 시간을 answer에 기록한다.
def solution(prices):
answer = [0 for _ in range(len(prices))]
stack = []
for idx, price in enumerate(prices):
if stack == []:
stack.append((idx, price))
else:
if price < stack[-1][1]:
while stack != [] and stack[-1][1] > price:
answer[stack[-1][0]] = idx-stack[-1][0]
stack.pop()
stack.append((idx,price))
while stack != []:
val = stack.pop()
answer[val[0]] = len(prices)-val[0]-1
return answer
효율성 테스트마저 한번에 클리어.
근데 로 풀어도 효율성 통과가 가능하긴 하더라...