[파이썬] 스택 - 일일 온도(리트코드 739)

본 포스팅은 '파이썬 알고리즘 인터뷰(책만, 박상길)을 참조함

1. 문제 - 일일온도(리트코드 739)

- 문제: 매일 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라

    - Input: temperatures = [73,74,75,71,69,72,76,73]
    - Output: [1,1,4,2,1,1,0,0]

- 설명: 위 온도 배열에서 첫 번째 값은 73도이고 그 다음은 74도다. 날씨가 더 따뜻해지려면 1일만 기다리면 되므로 출력값은 ‘1’이된다.

2. 풀이 - 스택 값 이용

개요

전체적인 풀이 과정은 아래와 같다

1. (for 반복문) for 반복문으로 온도 리스트를 참조한다.
2. (스택) 이를 통해 요소의 인덱스를 스택에 저장한다.
3. (while문) 현재 온도(for문)가 이전 온도(스택)보다 큰지 여부를 판단한다
4. (결과값) 현재 온도와 이전 온도의 인덱스 차이(=날짜 차이)를 리턴한다

해설

우선 아래 그림으로 연산 과정을 살펴보겠다.

F’는 입력값인 온도 리스트를 말한다. 

for 문을 통해 인덱스5(온도 72)가 참조 되었다고 하자.

이 때, 인덱스5보다 기온이 낮은 인덱스4(69도)와 인덱스3(71도)는 스택에서 대기를 하고 있는 상태다. 

‘for문이 가리키는 인덱스 5의 온도’가 ‘스택의 마지막 값이 가리키는 인덱스4’의 온도보다 크기 때문에

인덱스4는 스택에서 제거되고 인덱스5와 인덱스4의 차이값(날짜 차이) 1이 출력된다.

스택에서 인덱스4가 출력된 후, 스택의 맨 마지막에는 인덱스 3이 남게된다.

while문을 통하여 앞서 말한 과정과 동일하게 인덱스5와 인덱스3 간의 날짜 차이가 구해진다.

코드

def dailyTemperatures(self, temperatures):
  """
  :type temperatures: List[int]
  :rtype: List[int]
  """

  stack = []

  result = []

  for i, f in enumerate(temperatures):

      # 현재 온도 > 스택 온도 => (인덱스)거리를 정답으로 등록
      while stack and temperatures[stack[-1]] < f:
          prev = stack.pop()
          result[prev] = i - prev

      stack.append(i)
      result.append(0)

  return result