[DSA][Stack] 04. Daily Temperatures

LeetCode 739

 

04. Daily Temperatures

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.

 

 

[질문하기]

- 현재 온도와 같은 날도 더 따뜻한 날로 간주되나요, 아니면 strictly 따뜻한 날만 해당되나요?

 

 

[아이디어]

- stack을 사용해서 더 높은 날만 쌓고, idx를 통해 the number of days를 기록하자.

 

 

[풀이 1] Stack

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        res = [0] * len(temperatures)
        for idx, value in enumerate(temperatures):
            while stack and stack[-1][0] < value:
                old_idx = stack.pop()[1]
                res[old_idx] = idx - old_idx
            stack.append([value, idx])
        
        while stack:
            res[stack.pop()[1]] = 0
        
        return res

 

Brute Force 방식으로 문제를 접근해 보면, 각 ith 온도에 대해 뒤의 온도들을 모두 탐색하면서 가장 처음으로 온도가 높은 날을 만나면 간격을 저장하는 O(n^2) 풀이를 떠올릴 수 있다.

하지만 각 온도에 대해 더 따뜻한 날이 언제 올지를 찾는 대신, 현재 온도를 기준으로 이전에 나왔던 온도들 중 더 낮은 온도가 있었는지를 확인하는 방식으로 관점을 바꾸면 문제를 더 효율적으로 풀 수 있다. 매일의 온도를 확인하면서, 이전에 저장해둔 온도가 지금 온도보다 낮다면, 오늘이 더 따뜻한 날이 되므로 인덱스를 꺼내서 날짜 차이를 기록한다. 이 과정을 반복하면서, 이전의 더 낮은 온도들을 하나씩 꺼내고, 더 높은 온도만 남겨둔다면 내림차순의 형태로 온도들이 저장될 것이다.

이때 마지막 원소를 삭제하고, 삽입하는데 효율적인 자료구조가 필요하기 때문에 stack을 사용하는 것이다.

 

⏱️ 시간복잡도

배열을 한번 순회하며 push/pop 연산을 하는데, 이는 O(1)이기 때문에 총 시간 복잡도는 O(n)이다.

🧠 공간복잡도

최악의 경우 stack에 temperatures 길이만큼의 공간이 필요하므로 공간 복잡도는 O(n)이다.