[알고리즘] 프로그래머스 - 주식 가격
문제설명
https://programmers.co.kr/learn/courses/30/lessons/42584
처음에 생각한 해결법
- 주식 가격들을 저장할 스택을 선언한다. 스택에는
(인덱스, 현재가)
의 튜플이 들어간다. - 주식 가격 리스트를 순회하면서
현재가 < stack top의 price
라면 스택에 현재 가격을 push한다 - 그 반대의 경우라면, 스택을 pop하고,
인덱스 - stack top의 인덱스
(그러니까 주식 가격이 떨어지지 않은 시간)을answer
에 기록한다 - 주식 가격 순회가 끝나면 스택에 남은 원소들(끝까지 가격이 떨어지지 않은 것들)을 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
효율성 테스트마저 한번에 클리어.
근데 로 풀어도 효율성 통과가 가능하긴 하더라...
TIL
- 질문 목록에 있는 테케에서 잘못된 점을 깨닫긴 했지만 답을 본것은 아니었다. 꾸준히 알고리즘을 하니 그래도 성장이 보이는것 같아서 마냥 깜깜한 터널속을 지나는 기분만은 아닌 것 같다.
Author And Source
이 문제에 관하여([알고리즘] 프로그래머스 - 주식 가격), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@grefer/알고리즘-프로그래머스-주식-가격
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여([알고리즘] 프로그래머스 - 주식 가격), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@grefer/알고리즘-프로그래머스-주식-가격저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)