LeetCode - 739. Daily Temperatures [Python]

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

Daily Temperatures - LeetCode

---

풀이 과정

각 날짜의 온도가 주어질 때, 어떤 날짜에서 며칠을 기다려야 더 따뜻한 날이 되는지 출력하는 문제이다.

 

2중 for문 돌려서 O(N^2)로도 해결할 수 있겠지만, 스택을 활용해서 더 효율적으로 문제를 해결할 수 있다.

 

수의 index를 스택에 저장하면서, 스택탑의 index 날짜의 온도보다 더 따뜻한 날의 index가 들어오면 스택을 pop하면서 따뜻한 날의 index - 스택 탑의 index를 계산해서 정답 리스트에 저장해주면 문제를 해결할 수 있다. 

---

소스 코드

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        answer = [0 for _ in range(len(temperatures))]
        for a, b in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < b:
                last = stack.pop()
                answer[last] = a - last
            stack.append(a)
        return answer