739. Daily Temperatures

문제

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

예시

Input = [73, 74, 75, 71, 69, 72, 76, 73]

Output = [1, 1, 4, 2, 1, 1, 0, 0]

풀이

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack = []
        n = len(T)
        max_t = max(T)
        
        for i in range(len(T)-1):
            q = i + 1
            if T[i] == max_t: # 최대값일 때, (기온이 상승할 가능성이 없을 때)
                stack.append(0)
            elif i > 1 and T[i] == T[i-1]: # 바로 전 날과 기온이 같은 경우 (기온이 상승하는 날이 하루 빠름)
                if stack[-1] == 0:
                    stack.append(0)
                else:
                    stack.append(stack[-1]-1)
            else: # 다 계산해줘야하는 경우
                while T[i] >= T[q]:
                    q += 1
                    if q == n: # 끝까지 가버렸을 때, 
                        q = i
                        break
                stack.append(q-i)
            
        stack.append(0)
        return stack

모든 원소(기온)가 기온이 상승할 때까지 얼마나 걸리는 지를 구하는 문제이다. 자신의 기온보다 높은 기온을 찾기 위한 문제인데, 기온이 더 이상 상승할 수 없으면 0이 된다. 이 문제를 3가지 방법으로 접근했다.

• (if) 절대 기온이 상승할 수가 없는 경우 (기온이 이미 최대일 경우)
• (elif) 바로 전 날과 기온이 같은 경우 (바로 전 날보다 하루 빠르게 기온이 상승하는 경우)
• (else) 자신의 기온보다 높은 기온이 나올 때까지 탐색하는 경우

for문과 while문을 활용하게 되면 당연히 Time Limit이 나올 것이라 예상했고 역시는 역시 역시였다. 3가지 방법으로 접근하게 되면 Time Limit은 해결할 수 있으나, error에 초점을 맞춘 느낌은 지울 수가 없긴 하다. 그래서 다른 풀이를 찾아봤는데 이렇게 깔끔할 수가 없다..

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack = []
        ans = [0] * len(T)
        for i, t in enumerate(T):
            while stack and t > T[stack[-1]]:
                last = stack.pop()
                ans[last] = i - last
            stack.append(i)
        return ans

굉장히 깔끔한데 처음에 코드만 보고 이해를 하지 못했다..ㅠ

결과

37 / 37 test cases passed.
Status: Accepted
Runtime: 656 ms
Memory Usage: 17.4 MB