[LeetCode] 739. Daily Temperatures

말하는 감자·2024년 11월 11일

leetcode python stack 리트코드 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

6/32

오늘 문제를 살펴보겠습니다.

1. 오늘의 학습 키워드

LIFO
Stack

2. 문제: 739. Daily Temperatures

단계: Medium
주제: Array, Stack, Monotonic Stack
출처: https://leetcode.com/problems/daily-temperatures/description/

Description

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

1 <= temperatures.length <= $10^5$
30 <= temperatures[i] <= 100

3. 문제 풀이

매일의 온도를 나타내는 정수 배열 temperatures 이 주어졌을 때, answer 배열의 원소 answer[i] 는 i번째 날의 온도보다 더 따뜻해지기까지 며칠을 기다려야 하는지를 나타냅니다. 만약 더 따뜻해지는 날이 없다면 answer[i]==0 입니다. 이 상황에서 answer 배열을 반환하는 함수를 구하는 문제입니다.

문제를 차근차근 접근해보겠습니다.

Step1. 문제 이해하기

Input:
- 온도를 나타내는 정수 배열 temperatures 이 주어집니다. 이 배열의 길이는 1부터 $10^5$ 이므로 빈 배열은 아니며, 완전 탐색으로 풀면 시간 초과가 날 것입니다. 따라서 완전 탐색 풀이로는 풀 지 못할것 같습니다.
- temperatures[i] 값의 크기가 30이상 100이하인데, 이것은 시간 복잡도에는 큰 영향을 미치지 않습니다.
Output:
- answer 배열은 Input인 temperatures 의 길이와 동일해야 합니다.
- answer 배열은 temperatures 의 인덱스에 해당하는 값과 동일한 인덱스에서 값을 나타내야 하므로 정렬을 하면 안됩니다.

Step2. 접근 방법

Step1에서 Input과 Ouput을 제약 조건과 함께 분석을 진행했습니다. temperatures 배열은 정수 배열로써, 정렬을 사용하면 안됩니다. 또한 완전 탐색을 통해서 풀 수는 있지만 시간 초과가 날 것입니다.

하지만, 완전 탐색을 통해 문제를 어떻게 접근해야 할 지 보일수가 있기 때문에 완전 탐색을 생각해보았습니다.

temperatures 배열을 처음 인덱스, 처음 인덱스 + 1로 이중 반복문을 돌려서, temperatures[처음 인덱스 + 1] - temperatures[처음 인덱스] 가 0보다 크면 더 따뜻한날인것을 의미하기 때문에 며칠인지는 인덱스 끼리의 차를 통해 구할수 있습니다.

여기서, 무언가 느낌을 알아차리셨나요? 현재 온도보다 더 높은 온도가 나올 때까지의 날짜 차이를 구하려면, 뒤에서부터 값을 순서대로 처리하는 LIFO구조가 적합하다는 것입니다.

즉, temperatures 배열의 인덱스를 왼쪽에서 오른쪽으로 순회하면서 스택을 사용하여 현재 인덱스의 값보다 높은 온도를 만날 때까지 스택에 쌓아두고, 높은 온도를 만다면 스택에서 pop하면서 그 차이를 계산해나가는 방식이 필요한 것이죠.

이렇게 스택을 활용하여 현재 날짜보다 앞에 쌓인 날짜들의 온도를 빠르게 처리할 수 있고, 그 결과로 더 따뜻한 날까지의 날짜 차이를 효율적으로 구할 수 있습니다. 스택 자료구조를 활용하기 때문에 시간복잡도는 $O(n)$ 이 나올것으로 예상됩니다.

그럼, 코드 설계를 해보겠습니다.

Step3. 코드 설계

스택 초기화: temperatures 배열의 각 인덱스를 순회하면서 더 따뜻한 날을 찾을 때 까지 인덱스와 온도를 저장합니다. 인덱스와 온도를 저장하기 위해서는 temperatures 배열을 enumerate를 사용하여 반복문을 돌립니다.
answer 배열 초기화: temperatures 길이만큼 0으로 채워진 리스트를 생성합니다.
스택과 현재 온도 비교:
1. 현재 온도가 스택의 상단에 있는 인덱스가 가리키는 온도보다 높다면, 스택의 상단 값을 pop하여 온도 차이를 구합니다.
2. 이 과정을 반복하여 더 따뜻한 날이 나올 때마다 해당 인덱스의 값을 채워나갑니다.
temperatures 배열 순회가 끝난 후, 스택에 남아 있는 인덱스는 더 따뜻한 날이 없는 날들이므로 answer 배열에서 해당 인덱스에 0으로 유지합니다.

설계 내용을 바탕으로 코드 구현을 해보겠습니다.

Step4. 코드 구현

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        ans = [0] * len(temperatures)
        stack = []

        for day,temp in enumerate(temperatures):

            while stack and stack[-1][1] < temp:
                prev_day, _ = stack.pop()
                ans[prev_day] = day - prev_day

            stack.append((day,temp))
        return ans

코드 설명:

스택과 answer 배열 초기화: answer 배열은 temperatures 배열과 길이가 같으며, 모든 요소를 0으로 초기화합니다. 스택은 빈 리스트로 시작합니다.
반복문을 통한 탐색:
- enumerate 함수를 사용해 temperatures 배열을 (day, temp) 형태로 순회합니다.
- 현재 온도(temp)가 스택의 상단에 있는 인덱스의 온도보다 높은 경우:
  - 스택의 상단 요소가 현재 temp보다 낮다면, stack.pop()으로 이전 day 값을 가져와 현재 day와의 차이를 계산합니다.
  - 이 차이를 answer[prev_day]에 저장하여, prev_day부터 더 따뜻해지기까지 기다려야 하는 날짜 수를 기록합니다.
- 스택에 현재 (day, temp)를 추가하여, 이후 날짜의 온도와 비교할 준비를 합니다.
최종 결과 반환:
- 모든 temperatures 요소를 순회한 뒤, answer 배열에는 각 날짜마다 다음으로 더 따뜻해질 날까지의 날짜 수가 저장됩니다.
- 더 따뜻해질 날이 없는 경우에는 초기 값인 0이 그대로 유지됩니다.

이 방식은 스택을 통해 현재보다 낮은 온도들의 인덱스만 남겨두고, 더 높은 온도를 만나면 계산하고 pop하는 구조이므로 O(n)의 시간 복잡도로 동작합니다.

시간 복잡도: $O(n)$

결과:

https://leetcode.com/problems/daily-temperatures/submissions/1449366244

4. 마무리

이번 문제는 스택을 활용한 대표적인 Monotonic Stack 문제였습니다. 현재 날짜의 온도와 비교하여 더 따뜻한 날이 나올 때까지의 날짜 차이를 계산해야 했기 때문에, 최적의 접근 방식으로 스택을 선택할 수 있었습니다. 완전 탐색의 방식으로도 해결할 수 있지만, 반복되는 작업이 많아 시간 복잡도가 높아지게 되므로 효율적인 풀이가 되지 않습니다.

Monotonic Stack은 단조 증가 또는 감소하는 값들만 남겨두기 때문에 필요 없는 중간 단계를 제거하면서 효율적으로 문제를 해결할 수 있는 중요한 테크닉입니다. 특히, 이전 값들과 비교해 조건을 만족하는 시점에서의 값을 찾는 문제에서 매우 유용합니다.

이번 문제를 통해 스택을 활용해 데이터를 효율적으로 관리하고, 필요한 조건에서만 값을 처리하는 방법을 연습할 수 있었습니다.

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!!