[리트코드(LeetCode)] 739번 Daily Temperatures

문제

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

Daily Temperatures - LeetCode

온도 리스트를 입력받아서, 더 따뜻한 날씨를 위해서 며칠을 더 기다려야 하는지를 출력하는 문제다.

예시

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]

 

풀이

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

        for i, cur in enumerate(temperatures):
            while stack and cur > temperatures[stack[-1]]:
                last = stack.pop()
                ans[last] = i - last
            stack.append(i)

        return ans

 

- 각 날짜에 대해 높은 온도가 나타나기까지 기다려야 하는 문제로 스택을 사용한다.

- 현재의 인덱스를 스택에 쌓아두다가 온도가 상승한 지점에서 상승한 온도와 스택에 쌓아둔 인덱스 지점 차이를 리스트에 저장한다.

- 위의 방법을 반복 후 결과 리스트를 반환한다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview