문제설명

https://programmers.co.kr/learn/courses/30/lessons/42584

처음에 생각한 해결법

1. 주식 가격들을 저장할 스택을 선언한다. 스택에는(인덱스, 현재가)의 튜플이 들어간다.
2. 주식 가격 리스트를 순회하면서 현재가 < stack top의 price 라면 스택에 현재 가격을 push한다
3. 그 반대의 경우라면, 스택을 pop하고, 인덱스 - stack top의 인덱스 (그러니까 주식 가격이 떨어지지 않은 시간)을 answer에 기록한다
4. 주식 가격 순회가 끝나면 스택에 남은 원소들(끝까지 가격이 떨어지지 않은 것들)을 answer에 기록한다.

외않데?

아 정말 알고리즘이란 할수록 느는게 맞구나 라고 생각하면서 당당하게 채점을 했는데 테케 1번만 빼고 전부 틀렸다.
당연히 내 로직은 틀리지 않았다는 자만심으로 코드를 훓어보다 문득 스치는 생각이...

왜 스택의 top만 pop하는거지...?

파훼법 (이라고 할거까진 없지만ㅎ)

예를 들어 prices = [1, 2, 3, 2, 3, 1] 이라면, 두번째로 1을 만날 때에 (그러니까 idx==5) 모든 2와 3에 대해서 시간이 기록되어야 한다. (하락이 시작되었으므로) 그러나 나의 코드에서는 맨 위의값만 단 한번 pop 하기 때문에 당연히 틀린 논리로 코드를 작성했고, 운좋게 테케만 맞았던 것 뿐이다.

그래서 처음에 생각한 해결법의 3번을 다음과 같이 수정하였다.

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

효율성 테스트마저 한번에 클리어.
근데 $O(n^2)$로 풀어도 효율성 통과가 가능하긴 하더라...

TIL

• 질문 목록에 있는 테케에서 잘못된 점을 깨닫긴 했지만 답을 본것은 아니었다. 꾸준히 알고리즘을 하니 그래도 성장이 보이는것 같아서 마냥 깜깜한 터널속을 지나는 기분만은 아닌 것 같다.