739. Daily Temperatures Python3

Yelim Kim·2021년 10월 1일
0

Python Algorithm Interview

목록 보기
22/36
post-thumbnail

Problem

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 <= 105
30 <= temperatures[i] <= 100

My code

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

        n, right_max = len(T), float('-inf')
        res = [0] * n
        for i in range(n-1, -1, -1):
            t = T[i]
            if right_max <= t:
                right_max = t
            else:
                days = 1
                while T[i+days] <= t:
                    days += res[i+days]
                res[i] = days
        return res

Review

[실행 결과]
Runtime: 1196 ms , Memory Usage: 25.6 MB

[접근법]
거꾸로 세면서 최대값을 비교해서 저장한다.
해당 온도가 최대값이 아니라면 res 해당 인덱스에 일수를 하나씩 올려 기록한다.

[느낀점]
처음에는 순방향으로 해결하려고 했는데 자꾸 시간 오류나서 힌트를 참고하여 거꾸로 방법을 사용했다. 최대값을 비교하기 훨씬 쉬웠음.
아니 오늘 문제들 왜이렇게 어려운거야.......... 문제 이해하는데 이렇게 오래걸린적 처음이다... 늘었다는 말 취소...

profile
뜬금없지만 세계여행이 꿈입니다.

0개의 댓글