Python 알고리즘 인터뷰 - 문제22. 일일 온도

leetcode 739. Daily Temperatures - https://leetcode.com/problems/daily-temperatures/description/

 

매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야하는지를 출력하라

 

예제1

입력

T = [73, 74, 75, 71, 69, 72, 76, 73]

 

출력

[1, 1, 4, 2, 1, 1, 0, 0]

 

풀이

다음의 표에서 볼 수 있듯이 현재 온도가 이전의 온도보다 작은 경우 값을 인덱스를 스택에 저장해두었다가 스택의 top의 인덱스 값보다 더 큰 값이 들어올 경우 인덱스의 차이 만큼 기간을 계산하여 answer에 값을 저장한다.

 

다음과 같이 스택의 top보다 더 작은 값이 들어올 경우 값을 쌓아나간다. 이를 통해 더 온도가 낮은 값들이 온도가 높은 값을 만났을 때 계산할 준비를 할 수 있게 된다. 

현재의 온도가 stack의 top의 온도보다 높다면 해당 스택을 pop하여 기간 계산을 진행한다.

스택에는 index가 저장되 있으므로, 현재 인덱스 i와 스택의 top의 인덱스 last 의 차이를 계산하여 기간을 구하고 결과를 저장하는 answer 배열의 last에 인덱스에 기간을 저장한다.

코드는 다음과 같다.

def dailyTemperatures(self, temperatures):
    answer = [0] * len(temperatures)
    stack = []
    for i in range(len(temperatures)):
        while stack and temperatures[i] > temperatures[stack[-1]] :
            last = stack.pop()
            duration = i - last
            answer[last] = duration

        stack.append(i)

    return answer