[LeetCode | Python] 739. 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.

주어진 온도 배열에서, 각 날 이후 더 따뜻한 날이 오기까지 며칠을 기다려야 하는지 계산하는 문제이다.
 
 

풀이1: 브루트 포스

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        res = []
        
        for i in range(len(temperatures)):
            count = 0
            for j in range(i+1, len(temperatures)):
                count += 1
                if temperatures[j] > temperatures[i]:
                    res.append(count)
                    break
                elif j == len(temperatures) - 1:
                    res.append(0)
                else:
                    continue
            if i == len(temperatures) - 1:
                res.append(0)
        
        return res

처음 풀이!
이중 반복문으로 모든 경우를 확인하는 방식이다.
각 온도에 대해 이후 온도를 하나씩 비교하므로 시간 복잡도는 O(n^2) 이다.
리트코드에선 시간 초과로 통과하지 못하였다.
 
 

풀이2: stack 이용

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        stack = []
        res = [0] * len(temperatures)
        
        for i in range(len(temperatures)):
            while stack and temperatures[stack[-1]] < temperatures[i]:
                prev_index = stack.pop()
                res[prev_index] = i - prev_index
            stack.append(i)
        return res

stack의 마지막 요소에는 비교 기준인 날의 인덱스가 존재하게 된다.
* 온도차를 계산할 필요 없음에 유의하자! stack에 temperature를 저장하지 않고 비교 기준인 인덱스를 저장하면 됨에 유의하자.
현재 온도가 스택에 저장된 마지막 날의 온도보다 크면, 결과 배열을 업데이트하고 스택에서 해당 날을 제거한다.
 
시간복잡도는 temperatures 를 한번 순회하므로 O(n)이다.
 
 
 

---

갑자기 추워진 날씨와 어울리는 문제 ☃️