링크 : https://leetcode.com/problems/daily-temperatures/

description

Given a list of daily temperatures T, 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 T = [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].

풀이

처음에 푼 코드 => 시간 초과 😱

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        result = [0] * len(T)
            
        for i in range(len(T)) :
            for j in range(i+1, len(T)) :
                if T[i] < T[j] :
                    result[i] = j-i
                    break
                    
        return result

설명

단순하게 생각해서 그냥 뒤에 있는 애들 중에 자기보다 큰 애가 있는지 체크하는 로직이었다. 시간초과가 뜬다…

최종 코드

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        result = [0] * len(T)
        stack = []
            
        for i,v in enumerate(T):
            while stack and stack[-1][1] < v:
                t = stack.pop()
                result[t[0]] = i - t[0]
            stack.append((i,v))    
    
        return result

설명

스택 구조를 활용하는 로직이다. 각 온도를 인덱스와 함께 튜플로 넣어두는데 자기보다 높은 온도가 있는 날에 의해 꺼내어진다. 꺼내어지지 못하는 날은 기본 초기값인 0으로 남게 된다.