[Leetcode] 739. Daily Temperatures

문제

https://leetcode.com/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked

풀이

N이 최대 10^5이므로 브루트포스로 접근했을 때인 O(N^2)으로는 Timeout이 남을 알 수 있다. 따라서 O(N), O(NlogN)을 생각하며 접근했다.

스택 카테고리의 문제이므로 스택을 활용해서 linear한 접근만을 하는 방법을 고민했고, 처음 제출한 풀이는 다음과 같다.

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

        for i, temp in enumerate(temperatures):
            # 지금 온도보다 작았던 곳들 정답 갱신
            while stack and stack[-1][1] < temp:
                idx, num = stack.pop()
                ans[idx] = i-idx
            
            stack.append((i,temp)) # (index, 온도)
        
        return ans

discussion을 보니 스택에 인덱스만을 넣어서 풀이가 가능한 것을 알았고, 이를 토대로 수정한 코드는 다음과 같다.

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

        for i, temp in enumerate(temperatures):
            # 지금 온도보다 작았던 곳들 정답 갱신
            while stack and stack[-1][1] < temp:
                idx, num = stack.pop()
                ans[idx] = i-idx
            
            stack.append((i,temp)) # (index, 온도)
        
        return ans

이러한 방법에 사용되는 스택을 monotonic stack(단조 스택)이라고 한다. 스택안을 내림차순 혹은 오름차순으로 유지하여 시간복잡도를 개선하는 것이다. 이러한 자료구조는 다양하게 쓰이진 않고 이번 문제와 같은 Next Greater Number 문제에서만 쓰인다고 한다.(정확히는 previous/next smaller/larger problem)