[Leetcode]739. Daily Temperatures

브루트 포스로 풀면 시간초과가 나는 문제였다. 스택을 이용하는 문제라는 힌트는 봤는데 어떤 방식으로 문제를 풀어야할지 감이 잡히지 않았다.

스택으로 인덱스를 저장하는 아이디어를 이용했다.

스택으로 인덱스를 저장하면서 현재 값보다 작은 값을 가지는 인덱스가 스택에 존재하면 pop을 하면서 ans 배열에 그 인덱스의 차를 저장하여 푸는 문제였다.

def dailyTemperatures(self,T:List[int])->List[int]:
        ans = [0 for i in range(len(T))]
        stack = []
        for i,cur in enumerate(T):
            while stack and T[stack[-1]] < cur:
                idx = stack.pop()
                ans[idx] = i - idx
            stack.append(i)
        return ans