[프로그래머스 Lv.2] 주식가격

문제 링크: 프로그래머스 Lv.2 주식가격

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

 

인덱스 curIdx를 통해 주식 가격 리스트를 읽어나가면서, 스택에 현재 가격과 인덱스를 묶어서 push한다. 그러다가 현재 가격이 스택 맨 위의 가격보다 같거나 낮으면, 이는 주식 가격이 떨어졌다는 것을 의미하므로, 스택의 원소들을 pop한다. 현재 시점(curIdx)과 기록된 시점(topIdx)의 차이가 곧 '가격이 떨어지지 않은 기간'이며, pop한 원소의 인덱스야말로 우리가 구하는 answer의 인덱스이기에, answer[Idx] = curIdx - topIdx를 실행한다. 그러다가 스택 맨 위의 가격이 현재 가격보다 같거나 낮으면, 현재 가격은 더 이상 '떨어진 가격'이 아니기에 pop을 멈춘다.

주식 가격 리스트의 모든 원소를 읽었는데도 스택에 남은 원소가 있다면 해당 원소는 '자기보다 낮은 가격이 나온 적 없는 가격'이다. curIdx를 마지막 시점(len(prices)-1)로 설정한 후 pop하듯이 읽어나간다.

내 기억으로는 이와 비슷한 풀이로 모 기업의 코딩테스트를 봤던 것 같은데.. 속도가 많이 느렸다고 한다. 지금도 뭐가 문제인지 모르겠는데, 그 때 잘못 풀었던 것일지 아니면 지금도 뭔가 부족한 풀이인지에 대해서 좀 더 생각해봐야겠다. 친구는 이 문제에 대해서 신박하게도 Min Heap을 사용했다고 했는데, 그 풀이를 고민하면 답이 나오지 않을까?

 

def solution(prices):
    TOP = -1
    PRICE = 0
    IDX = 1

    answer = [0] * len(prices)
    stack = []

    for curIdx in range(0, len(prices)):
        curPrice = prices[curIdx]

        # stack이 비어있으면 무조건 push
        # stack[top][price]보다 같거나 높은 가격이 들어오면 push
        if len(stack) == 0 or curPrice >= stack[TOP][PRICE]:
            stack.append((curPrice, curIdx))
            continue

        # stack[top]의 가격 미만의 가격이 들어오면
        while True:
            if len(stack) == 0: break
            
            # stack[top]의 가격이 curPrice보다 낮은 것이 나올 때까지 pop
            if stack[TOP][PRICE] <= curPrice: break
            topPrice, topIdx = stack.pop()
            answer[topIdx] = curIdx - topIdx
        stack.append((curPrice,curIdx))
    
    # 끝났는데 스택에 남아있으면
    curIdx = len(prices) - 1
    for item in stack:
        answer[item[IDX]] = curIdx - item[IDX]
    
    return(answer)