LeetCode

LeetCode 739 Daily Temperatures 풀이: 단조 스택으로 다음 따뜻한 날 찾기

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

각 날짜마다 미래에 처음으로 더 높은 온도가 나오는 날까지의 간격을 구해야 한다. 모든 미래 날짜를 다시 확인하면 O(n²)이 되므로, 아직 답을 찾지 못한 날짜를 스택에 보관하고 현재 온도로 답을 확정하는 단조 스택 발상이 필요해 Level 3으로 판단했다.

1. 단조 스택으로 다음 따뜻한 날 찾기

temperatures[i]가 i번째 날의 온도를 나타낼 때, 각 날짜 이후 처음으로 더 따뜻한 날이 나타날 때까지 며칠을 기다려야 하는지 배열에 저장한다. 미래에 더 따뜻한 날이 없으면 해당 위치에 0을 저장한다.

문제의 조건은 다음과 같다.

  • 온도 배열의 길이는 1 이상 10^5 이하다.
  • 각 온도는 30 이상 100 이하다.
  • 더 따뜻한 날은 현재 온도보다 엄격하게 높아야 한다.
  • 결과는 온도 배열과 같은 길이다.

예를 들어 [73, 74, 75, 71, 69, 72, 76, 73]에서는 첫날 다음 따뜻한 날이 다음 날이므로 첫 번째 결과는 1이다. 네 번째 날의 온도 71은 이틀 뒤 72를 만나므로 결과가 2다.

2. 스택을 활용해보자

상태 전이와 경계 처리

결과 배열 answer은 모두 0으로 초기화함. 더 따뜻한 날을 찾지 못한 날짜의 인덱스를 스택에 저장한다. 스택에는 아래에서 위로 갈수록 온도가 같거나 낮아지는 인덱스만 남긴다.

현재 날짜 i의 온도 temperature를 읽을 때 다음과 같이 처리한다.

  1. 스택이 비어 있지 않고 현재 온도가 스택 top 날짜보다 높으면 top 인덱스를 꺼낸다.
  2. 현재 날짜 i가 꺼낸 날짜의 첫 번째 더 따뜻한 날이므로 answer[previous] = i - previous로 기록한다.
  3. 현재 온도보다 낮은 날짜가 스택 top에 올 때까지 이 과정을 반복한다.
  4. 현재 인덱스 i를 스택에 넣어 미래의 더 따뜻한 날을 기다린다.

끝까지 스택에 남은 날짜는 더 따뜻한 날을 찾지 못한 날짜다. 결과 배열을 0으로 시작했으므로 이 인덱스들을 따로 처리하지 않아도 된다.

현재 온도가 확정하는 대기 날짜

스택에는 아직 더 따뜻한 날을 만나지 못한 인덱스만 남는다. 현재 온도가 top보다 높아지면 현재 날짜가 top 인덱스의 첫 번째 따뜻한 날이다. 이를 확인한 뒤에도 더 낮은 대기 온도가 남아 있을 수 있으므로, 현재 온도가 top 이하가 될 때까지 계속 꺼낸다.

예를 들어 temperatures = [73, 74, 71, 72]라면 인덱스 1의 74가 인덱스 0의 답을 바로 확정한다. 뒤이어 71은 74보다 낮으므로 대기 스택에 남고, 72를 만나는 순간 인덱스 2의 답도 확정된다.

현재 온도와 같은 값은 더 따뜻한 날이 아니므로 비교는 엄격한 >여야 한다. >=를 쓰면 같은 온도를 하락/상승으로 잘못 처리해 답을 너무 일찍 확정한다. 인덱스는 한 번 들어가고 한 번 나올 뿐이므로, 이 구조가 중복 탐색을 없애며 전체 시간 복잡도를 O(n)으로 만든다.

시간·공간 복잡도

모든 인덱스가 최대 한 번 push되고 한 번 pop되므로 시간 복잡도는 O(n)이다. 결과 배열과 스택에 최대 n개의 원소가 저장되므로 공간 복잡도는 O(n)이다. 결과 배열은 문제에서 반드시 반환해야 하므로, 결과를 제외한 보조 스택 공간도 O(n)이다.

3. 문제 해결 코드 (Python)

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        answer = [0] * len(temperatures)
        stack = []

        for current_day, current_temperature in enumerate(temperatures):
            while stack and current_temperature > temperatures[stack[-1]]:
                previous_day = stack.pop()
                answer[previous_day] = current_day - previous_day

            stack.append(current_day)

        return answer

스택에는 온도 자체가 아니라 인덱스를 저장한다. 인덱스가 있어야 결과 위치를 갱신하고 현재 날짜와의 차이를 계산할 수 있으며, 실제 온도 비교는 temperatures[index]로 수행할 수 있다. 마지막까지 답이 확정되지 않은 위치는 초기값 0이 그대로 남는다.

4. 오답 접근과 반례

모든 미래 날짜를 매번 확인하기

각 날짜에서 오른쪽을 끝까지 순회해 처음으로 높은 온도를 찾는 방식은 간단하지만 최악의 경우 O(n²) 시간이 필요하다.

temperatures = [30, 29, 28, 27, ..., 100]

많은 날짜가 뒤쪽의 같은 높은 온도를 찾기 위해 긴 구간을 반복해서 확인한다. 배열 길이가 최대 10^5이므로 각 날짜의 미래를 다시 순회하는 방식은 비효율적이다.

더 높거나 같은 온도를 정답으로 처리하기

다음 입력에서 같은 온도는 더 따뜻한 날이 아니다.

temperatures = [30, 30, 31]
정답 = [2, 1, 0]

첫 번째 30의 답은 바로 다음 날이 아니라 이틀 뒤의 31이다. 따라서 스택에서 꺼내는 조건은 current_temperature > temperatures[stack[-1]]처럼 엄격한 대소 비교여야 한다.

스택에 온도만 저장하기

온도만 저장하면 어떤 결과 배열 위치를 갱신해야 하는지 알 수 없고, 현재 날짜와의 간격도 계산할 수 없다. 온도 비교에 필요한 값은 배열에서 다시 읽고, 스택에는 날짜 인덱스를 저장해야 한다.

현재 날짜를 먼저 스택에서 제거하기

현재 날짜는 아직 미래의 따뜻한 날을 기다리는 상태이므로, 이전 날짜들을 해결한 뒤 스택에 추가해야 한다. 현재 인덱스를 먼저 넣으면 자기 자신과 비교하거나 날짜 순서가 꼬일 수 있다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 상승·하락·같은 온도 경계를 확인할 수 있다.

solver = Solution()
assert solver.dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
assert solver.dailyTemperatures([5, 5, 5]) == [0, 0, 0]
assert solver.dailyTemperatures([5, 4, 3]) == [0, 0, 0]

5. 공식 예제와 추가 검증

작성한 dailyTemperatures 함수를 Python으로 실행해 공식 예제와 경계 사례를 확인했다.

공식 예제

입력 기대 출력 확인 결과
[73,74,75,71,69,72,76,73] [1,1,4,2,1,1,0,0] 통과
[30,40,50,60] [1,1,1,0] 통과
[30,60,90] [1,1,0] 통과

추가 검증 1: 하루만 있는 경우

입력: temperatures = [30]
기대 출력: [0]
확인 결과: 통과
검증 목적: 미래 날짜가 없는 최소 입력을 확인

추가 검증 2: 계속 내려가는 온도

입력: temperatures = [35, 34, 33, 32]
기대 출력: [0,0,0,0]
확인 결과: 통과
검증 목적: 스택에 남은 모든 날짜의 기본값 0 처리를 확인

추가 검증 3: 같은 온도 건너뛰기

입력: temperatures = [30, 30, 31]
기대 출력: [2,1,0]
확인 결과: 통과
검증 목적: 같은 온도를 더 따뜻한 날로 처리하지 않는지 확인

추가 검증 4: 중간에서 여러 날짜를 한 번에 해결

입력: temperatures = [30,31,30,32]
기대 출력: [1,2,1,0]
확인 결과: 통과
검증 목적: 현재 온도 32가 앞의 대기 중인 여러 날짜를 올바르게 해결하는지 확인

6. 다른 풀이 방식 검색 및 비교

완전탐색은 각 날짜의 미래를 직접 확인해 이해하기 쉽지만 O(n²) 시간이 필요하다. 오른쪽에서 왼쪽으로 이동하며 이미 계산한 결과를 이용해 건너뛰는 동적 계획법도 O(n)에 해결할 수 있지만 점프 조건과 종료 상태를 관리해야 한다.

이 글에서는 아직 답을 찾지 못한 날짜를 스택에 모아 현재 온도가 답이 되는 순간 바로 확정하는 단조 스택을 사용했다. 각 인덱스가 한 번씩만 들어가고 나오므로 구현과 선형 시간 근거를 함께 설명하기 쉽다.

마무리

Daily Temperatures는 각 위치에서 미래를 반복해서 검색하는 대신, 아직 더 따뜻한 날을 기다리는 날짜를 단조 스택으로 관리하는 문제다. 현재 온도가 스택의 온도보다 높아지는 순간 날짜 차이를 기록하고 현재 인덱스를 다시 스택에 넣으면, 모든 날짜를 O(n) 시간에 처리할 수 있다. 같은 온도는 정답이 아니므로 반드시 엄격한 > 비교를 사용해야 한다.

#스택#LeetCode#난이도 3