[파이썬 알고리즘] 일일 온도

일일 온도

리트코드로 풀러 가기

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

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

출력: [1, 1, 4, 2, 1, 1, 0, 0]

이 문제는 리스트의 요소부터 끝까지 순회하도록 처리하여 풀 수도 있는데, 그렇게 처리하면 시간 복잡도가 O(n^2)가 되어서 타임아웃 될 수 있다.

스택을 이용한 풀이

주어진 리스트를 순회하며 스택에 리스트의 인덱스를 넣는다.

만약, 스택의 마지막 요소(온도 리스트의 인덱스)의 온도값이 현재 온도값보다 크다면(가장 최근의 온도보다 따뜻해졌다면) 스택을 pop하여 현재 따듯해진 값이 얼마의 과거의 인덱스 만큼 유효한지 검사한다.

그 겁사된 값(현재 인덱스와 과거의 인덱스의 차)를 미리 0으로 리셋시켜둔 answer리스트에 넣어주면 답이 된다.

def dailyTemperatures(self, T: List[int]) -> List[int]:
    if not T:
        return []
    answer = [0] * len(T)
    stack = []
    
    for i, cur in enumerate(T):
        while stack and (cur > T[stack[-1]]):
            last = stack.pop()
            answer[last] = i - last
        stack.append(i)
    
    return answer