리트코드 739번 Daily Temperature (Python)

Problem

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

Solution

1차 풀이

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        answer = {}
        for i, next_t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < next_t:
                idx = stack.pop()
                answer[idx] = i - idx
            stack.append(i)
        
        for i in stack:
            answer[i] = 0
        
        return [v[1] for v in sorted(answer.items())]

인덱스를 계속 쌓아두다가 현재의 온도가 스택의 온도보다 높아지는 것들을 모두 뽑아서 결과를 구하였다. 정답 리스트에 들어가는 순서는 인덱스 순서대로 들어가야 하지만 이 순서가 지켜지지 않아 dictionary를 이용하여 {idx: answer}형태로 넣었다. 이로 인해 마지막에 다시 정렬해야 해서 시간이 오래걸렸다.

2차 풀이

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

        return answer

dictionary 대신 0으로 초기화 되어 있는 list를 이용하여 시간과 메모리를 아낄 수 있었다.

Reference

파이썬 알고리즘 인터뷰 22번