Python 스택으로 풀어보는 일일 기온(Daily Temperatures) 문제

문제 개요

일일 기온 리스트 T가 주어졌을 때, 각 날짜마다 현재보다 더 따뜻한 기온이 나타날 때까지 며칠을 기다려야 하는지를 담은 리스트를 반환하는 문제입니다. 만약 이후에 더 따뜻한 날이 존재하지 않는다면 해당 위치에는 0을 저장합니다.

예를 들어 T = [73, 74, 75, 71, 69, 72, 76, 73]이라면 결과는 [1, 1, 4, 2, 1, 1, 0, 0]이 됩니다. 첫 번째 날(73도)은 바로 다음 날(74도)에 더 따뜻해지므로 1이고, 세 번째 날(75도)은 이후 기온이 잠시 내렸다가 여섯 번째 날(76도)에 처음으로 더 따뜻해지므로 4가 됩니다.

알고리즘 접근 방법

이 문제는 단조 감소 스택(monotonic decreasing stack)을 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 아직 더 따뜻한 날을 찾지 못한 날짜의 인덱스들을 스택에 쌓아 두고, 더 따뜻한 기온이 등장할 때마다 스택에서 꺼내며 거리를 계산하는 방식입니다.

해결 절차는 다음과 같습니다.

ans를 T와 같은 크기의 배열로 생성하고 모든 값을 0으로 초기화합니다.
스택을 하나 선언하고 인덱스 0을 삽입한 뒤, 탐색 인덱스 i를 1로 설정합니다.
i가 T의 길이보다 작은 동안 다음 과정을 반복합니다.
- 스택이 비어 있지 않고 T[i]가 스택 최상단 인덱스의 기온보다 큰 동안:
  - index에 스택 최상단 요소를 저장합니다.
  - ans[index]에 i − index를 대입합니다.
  - 스택에서 최상단 요소를 제거(pop)합니다.
- 스택이 비어 있거나 T[i]가 스택 최상단 인덱스의 기온보다 작거나 같으면 i를 스택에 삽입합니다.
- i를 1 증가시킵니다.
최종 결과 ans를 반환합니다.

Python 구현 예제

다음 코드를 통해 실제 구현을 살펴보겠습니다.

class Solution(object):
    def dailyTemperatures(self, T):
        ans = [0 for i in range(len(T))]
        stack = []
        stack.append(0)
        i = 1
        while i < len(T):
            while len(stack) and T[i] > T[stack[-1]]:
                index = stack[-1]
                ans[index] = i - index
                stack.pop()
            if not len(stack) or T[i] <= T[stack[-1]]:
                stack.append(i)
            i += 1
        return ans

ob1 = Solution()
print(ob1.dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))

동작 원리

스택에는 아직 더 따뜻한 날을 만나지 못한 날짜의 인덱스만 남아 있습니다. 새로운 기온이 스택 꼭대기의 기온보다 높으면, 그 사이의 날짜들은 모두 답을 찾은 것이므로 차례로 꺼내면서 대기 일수를 기록합니다. 각 인덱스가 최대 한 번씩만 push되고 pop되기 때문에 전체 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다.

실행 결과

입력

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

출력

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