[LeetCode] 739. Daily Temperatures (일일 온도)

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

일일 온도 T 목록이 주어지면 입력의 각 날짜에 대해 더 따뜻한 온도까지 기다려야하는 일 수를 알려주는 목록을 반환합니다. 이것이 가능한 미래 날이 없으면 대신 0을 입력하십시오.

✍️ 풀이

---

이전에 풀었던 42. Trapping Rain Water 와 비슷하게 스택으로 풀 수 있다.
현재의 인덱스는 일단 스택에 쌓는다. 그리고 가장 최근에 스택에 쌓인 온도보다 높은 온도가 나오면 현재 인덱스와 스택에서 꺼낸 인덱스의 차이가 기다려하는 일 수 이다.

🛠 코드

---

• stack에 현재온도와 인덱스를 모두 넣어서 풀었다. 사실 인덱스를 알면 온도를 알 수 있으니까 그렇게 할 필요가 없었다.

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

        for i in range(1, len(T)):
            while stack and stack[-1][0] < T[i]:
                val = stack.pop()
                ret[val[1]] = i - val[1]
            stack.append([T[i], i])

        print(ret)
        return ret

• enumerate를 이용해서 스택에는 인덱스만 넣고 문제를 해결했다. (좀 더 심플)

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

        for i, temp in enumerate(T):
            while stack and T[stack[-1]] < temp:
                index = stack.pop()
                ret[index] = i - index
            stack.append(i)
        return ret

---

📝 정리

---

🎈 참고

---

Book 링크