[LeetCode] 739. Daily Temperatures

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

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

---

접근 방법 (for문 중첩)

• temperatures 를 반복문으로 돌리면서 날짜마다 남은 temperatures 와 비교하는 반복문을 또 돌려 이중 for 문을 통해 구하려고 시도하였으나, 테스트케이스중에 배열의 길이가 3만인 케이스에서 시간 초과로 실패하였다.

---

접근 방법 (stack)

• 이전 316. Remove Duplicate Letters에서 사용하였던 것 처럼 리스트의 일부를 순회하기 위해 중첩된 for 문을 사용하는 대신 stack 을 이용하여 해결하였다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        days = [0] * len(temperatures)
        for i, temp in enumerate(temperatures):
            while stack and stack[-1][1] < temp:
                j = stack.pop()[0]
                days[j] = i - j
            stack.append([i, temp])
        return days

• 이 전과 마찬가지로, 미리 날짜를 담을 days 배열을 만든 뒤, 루프마다 해당 날짜 뒤의 모든 날짜를 순회하는 것이 아니라 해당 날짜의 인덱스와 온도를 스택에 push 하고, 다음 루프로 넘어가서 스택의 top과 그 다음 날짜의 온도를 비교하여 조건을 만족시켰으면 pop 을 한 후 인덱스를 계산하여 days 배열에 채워넣고, 조건을 만족시키지 못했으면 계속 스택에 push 하여 전체 스택을 다음 루프로 넘기는 방식으로 진행된다.

• 이런식으로 전체 배열을 돌며 특정 값과 나머지 배열을 모두 비교해야하는 문제에서 for 문을 중첩하여 사용하기보단 stack 을 적절하게 활용하는 방안을 찾아보는 것이 더 좋을 것 같다.