739. Daily Temperatures

Daily Temperatures - LeetCode

1. Monotone Stack

from typing import *


class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        index = [i for i in range(len(T))]
        new_list = list(map(lambda x, y: (x, y), index, T))
        stack, answer = [], []
        while new_list:
            cur = new_list.pop()
            if not answer:
                answer.append(0)
                stack.append(cur)
            else:
                while stack and stack[-1][1] <= cur[1]:
                    stack.pop()
                if not stack:
                    answer.append(0)
                    stack.append(cur)
                else:
                    answer.append(stack[-1][0] - cur[0])
                    stack.append(cur)
        return answer[::-1]

2. 리팩토링

from typing import *


class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        index = [i for i in range(len(T))]
        new_list = list(map(lambda x, y: (x, y), index, T))
        stack, answer = [], []
        while new_list:
            cur = new_list.pop()
            while stack and stack[-1][1] <= cur[1]:
                    stack.pop()
            if not stack:
                answer.append(0)
            else:
                answer.append(stack[-1][0] - cur[0])
            stack.append(cur)
        return answer[::-1]

 

Stack의 성질을 이용해 풀 수 있다.

주어진 배열은 왼쪽과 같다. -> [온도 1, 온도 2, 온도 3.... ] 

이 배열을 다음과 같이 변경한다. -> [(0, 온도 1), (1, 온도 2), (2, 온도 3)...]

그냥 주어진 배열에 인덱스 값만 추가해서 기존 위치를 기록한다.

 

그리고 만든 배열을 뒤집어서 마지막 날부터 처리를 한다.

 

1. 스택을 이용해 온도 값을 오름차순으로 정렬하고 현재 온도보다 stack의 tail의 온도가 클 때까지 pop을 한다.

2. 스택에 값이 없다는 것은 현재 시점 이후에 현재 온도보다 높은 온도가 없다는 뜻이니깐 0을 삽입한다.

3. 스택에 값이 있다는 것은 현재 시점 이후에 현재 온도보다 높은 온도가 있다는 뜻이니깐 (현재 스택의 tail 값의 인덱스 - 현재 온도의 인덱스) 값을 결과 배열에 저장한다. 이 값이 현재 시점에서 최초로 현재보다 온도가 높아지는(= 맑아지는) 날이 된다.

그리고 현재 온도를 stack에 저장한다.

 

시뮬레이션하면 다음과 같다.

주어진 온도
[73, 74, 75, 71, 69, 72, 76, 73]



초기 스택 [], 현재 온도 (7, 73)
현재 스택 [(7, 73)]
현재 결과 [0]

초기 스택 [(7, 73)], 현재 온도 (6, 76)
현재 스택 [(6, 76)]
현재 결과 [0, 0]

초기 스택 [(6, 76)], 현재 온도 (5, 72)
현재 스택 [(6, 76), (5, 72)]
현재 결과 [0, 0, 1]

초기 스택 [(6, 76), (5, 72)], 현재 온도 (4, 69)
현재 스택 [(6, 76), (5, 72), (4, 69)]
현재 결과 [0, 0, 1, 1]

초기 스택 [(6, 76), (5, 72), (4, 69)], 현재 온도 (3, 71)
현재 스택 [(6, 76), (5, 72), (3, 71)]
현재 결과 [0, 0, 1, 1, 2]

초기 스택 [(6, 76), (5, 72), (3, 71)], 현재 온도 (2, 75)
현재 스택 [(6, 76), (2, 75)]
현재 결과 [0, 0, 1, 1, 2, 4]

초기 스택 [(6, 76), (2, 75)], 현재 온도 (1, 74)
현재 스택 [(6, 76), (2, 75), (1, 74)]
현재 결과 [0, 0, 1, 1, 2, 4, 1]

초기 스택 [(6, 76), (2, 75), (1, 74)], 현재 온도 (0, 73)
현재 스택 [(6, 76), (2, 75), (1, 74), (0, 73)]
현재 결과 [0, 0, 1, 1, 2, 4, 1, 1]

[1, 1, 4, 2, 1, 1, 0, 0]

Process finished with exit code 0