LeetCode - 739. Daily Temperatures

[LeetCode] 739. Daily Temperatures

LeetCode 739번 문제를 풀어보았다.. Link

Problem

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.

Intuition

Check all the temperature one by one to see how many days it wait to get a warmer temperature.

Approach

처음에는 모든 케이스를 전부 비교하는 Brute Force 알고리즘으로 풀고자 했다. 손쉽게 중첩 for loop을 사용하여 구현할 수 있었지만,

제출하니까 Time limit exceeded..

결국 더 최적화된 알고리즘을 사용해야했다.

이에 고민하다가 이전 최대 온도값의 위치를 기억하여 다음 반복 시 그 시작 위치를 조절해주는 방법을 사용했지만,

이것 역시도 불필요한 반복이 많이 발생했고 그로인해 Time limit exceeded 되었다.

고민하던 중 Stack을 사용한다면 위와 같은 접근법을 사용하면서도 불필요한 반복 (최대 온도값과 현재 온도값을 주기적으로 비교하는)을 줄일 수 있을 거라고

생각하였고, 코드로 옮겨 실행한 결과 정답이었다.

Complexity

• Time complexity:

  정확한 Time complexity를 알 수 없으나 대략 \(O(n^2)\)인 것으로 생각된다.

• Space complexity: \(O(n)\)

My Code

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        """
        Input: array of "temperatures" which represents the daily temperatures
        Output: An array "answer" such that answer[i] is the number of days
        i have to waith after the 1th day to get a warmer temperature
        """
        stack = []
        answer = [0] * len(temperatures)

        for idx, cur_t in enumerate(temperatures):
            while stack and cur_t > temperatures[stack[-1]]:
                last = stack.pop()
                answer[last] = idx - last
            stack.append(idx)
        return answer

Others (Brute force)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        """
        Input: array of "temperatures" which represents the daily temperatures
        Output: An array "answer" such that answer[i] is the number of days
        i have to waith after the 1th day to get a warmer temperature
        """
        answer = []
        t_len = len(temperatures)
        for i in range(t_len):
            for j in range(i, t_len):
                if temperatures[i] < temperatures[j]:
                    answer.append(j-i)
                    break
                else:
                    if j == t_len - 1:
                        answer.append(0)
        return answer