[LeetCode]Daily Temperatures

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 온도에서 며칠 뒤에 따뜻해지는지를 구하는 문제입니다. 따뜻해지지 않는다면 0으로 설정합니다.

 

처음 시도한 답안

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

        for idx, temperature in enumerate(temperatures):
            while stack and stack[-1][1] < temperature:
                prev_idx, _ = stack.pop()
                output[prev_idx] = idx - prev_idx

            stack.append([idx, temperature])

        return output

접근 방법

1. Monotonic Stack(단조 스택)을 활용해 풀이할 수 있습니다. 
   단조 스택은 스택안의 요소가 오름차순 혹은 내림차순으로 정렬되어 있는 스택입니다.
2. output에는 주어진 온도가 며칠뒤에 따뜻해지는지를 기록하는 배열입니다.
3. temperatures 리스트를 순회합니다.
   1. 스택에 값이 있고 스택의 마지막 요소 < 등장한 온도인 경우에만 순회합니다.
      1. 이 경우는 스택에 들어있는 이전 요일의 온도보다 따뜻해진 경우입니다.
      2. 스택에서 pop 하여 이전 요일의 idx를 구합니다.
      3. output 리스트에 idx-이전 요일의 idx를 계산해 며칠만에 따뜻해졌는지를 기록합니다.
   2. 스택에 등장한 요일의 인덱스와 온도를 push 합니다.
4. 순회를 완료하면 output 리스트에 정답이 기록되어 있습니다.

 

temperatures = [30, 40, 35, 50, 60]로 예시를 들어 설명하겠습니다.

1. output = [0, 0, 0, 0, 0]로 초기화합니다.
2. 온도 배열을 순회하면서
   1. idx=0, temp=30 : 처음에는 스택에 아무런 값이 없기 때문에 [0, 30]을 푸시합니다.
      stack = [[0, 30]]
   2. idx=1, temp=40: 스택에 값이 있고 등장한 온도가 더 크기 때문에 스택에서 pop 합니다.
      prev_idx = 0, ouput[0] = 1 - 0 기록하고 스택에 푸시합니다.
      output = [1, 0, 0, 0, 0], stack = [[1, 40]]
   3. idx=2, temp=35 : 스택에 값이 있으나 등장한 온도가 더 작기 때문에 스택에 푸시만 합니다.
      stack = [[1, 40], [2, 35]]
   4. idx=3, temp=50 : 스택에 값이 있고 모두 등장한 온도보다 작기 때문에 모두 pop 합니다.
      prev_idx = 2, output[2] = 3 - 2 기록
      prev_idx = 1, output[1] = 3 - 1 기록
      output = [1, 2, 1, 0, 0], stack = []
   5. idx=4, temp=60 : 스택에 값이 없기 때문에 생략합니다.
3. 순회가 종료되면 output = [1, 2, 1, 0, 0]이 기록됩니다. 이처럼, 스택에는 계속해서 내림차순의 형태로만 저장이 되는 단조 스택의 성질을 띄게 됩니다.

 이 문제의 경우에는 스택을 활용해야 하는 것 까지는 쉽게 떠올릴 수 있었으나 푸시하고 pop하는 기준을 파악하는게 쉽지는 않았던 것 같습니다. 또한, 스택이 정렬되어있는 성질을 띄게되는 단조 스택이라는 개념도 공부할 수 있었습니다.