개요

LeetCode #739, Daily Temperatures 문제를 풀어봅니다.

Given a list of daily temperatures temperatures, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

초기 값은 0으로 다 채워놓습니다. 인덱스를 stack에 계속 쌓다가 현재 온도와 stack의 인덱스에 해당하는 온도를 비교해서 현재 온도가 높으면 stack의 인덱스를 pop으로 가져오고, 현재 인덱스와 stack에서 가져온 인덱스의 차이를 answer에 넣습니다. [73, 74, 75, 71, 69, 72, 76, 73]일 때 인덱스 5인 지점에서는 75를 넘는 것이 나오지 않았으니 75의 인덱스인 2부터 시작해서 stack에 [2, 3, 4]가 있습니다. 현재 인덱스 5인 72는 71, 69보다 크니까 71에 해당하는 답은 2고 69에 해당하는 답은 1이 됩니다. answer[3]은 2, answer[4]는 1이 됩니다. stack에서 pop 했으니 stack은 [2]만 남습니다. 인덱스 5가 일단 추가되어 [2, 5]가 될 것입니다. 인덱스 6으로 넘어가서 76이 나왔으니 75, 72보다 모두 크고 stack은 전부 비워집니다. 72의 경우 현재 인덱스와 pop으로 가져온 것 차이가 1이니 answer[5]는 1입니다. 75의 경우 현재 인덱스와 pop으로 가져온 것 차이가 4이니 answer[2]는 4입니다. 남은 76, 73은 끝까지 더 높은 온도가 없으니 0으로 끝납니다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []
        for i, cur in enumerate(temperatures):
	        # 현재 온도 > stack 값
            while stack and cur > temperatures[stack[-1]]:
                last = stack.pop()
                answer[last] = i - last
            stack.append(i)
        
        return answer