[leetcode] 739. 일일 온도 (Daily Temperatures)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

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.

 

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

 

화씨 73도인 첫째 날에서 더 따뜻한 날을 위해서는 하루만 기다리면 된다. 바로 다음날인 둘째 날은 화씨 74도다. 마찬가지로 더 따뜻한 날을 위해서는 셋째 날까지 하루만 기다리면 된다. 셋째 날은 화씨 75도며, 이보다 더 따뜻한 날을 위해서는 4일을 더 기다려야 일곱째 날 화씨 76도가 된다. 일곱째 날과 여덟째 날은 더 이상 따뜻한 날이 없으므로 각각 0이다.

 

 

입출력 예시

Example 1:

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

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

 

생각과정

문제는 이해가 됐다. 현재 포인터 기준으로 포인터보다 큰 값이 몇번째 후에 있는 지 찾는 문제이다.
이제 이걸 stack으로 어떻게 접근하느냐... 모르겠으니 해답을 보자.

 

풀이

def dailyTemperatures(temperatures: List[int]) -> List[int]:
    # 정답을 담기 위한 리스트 생성
    answer = [0] * len(temperatures)

    # 인덱스를 추가하기 위한 stack 생성
    stack = []

    # enumerate() 함수를 사용해서 인덱스와 값을 둘다 뽑아온다.
    for i, cur in enumerate(temperatures):
        # stack가 있으면서 현재의 온도가 전 날 온도보다 높은 경우
        while stack and cur > temperatures[stack[-1]]:
            # stack에 담아줬던 첫번째 날의 인덱스를 꺼내와서 last 변수에 담아준다.
            last = stack.pop()

            # answer의 last번째 인덱스에(이번 for문이 돌아가기 전 index가 last에 담겨있다.) 현재의 인덱스 - last 인덱스를 넣어준다.
            # i에 last를 빼주는 이유? while 조건에서 현재의 날씨가 전날의 날씨보다 낮은 경우 while문을 건너뛰고 stack에 계속 쌓아준다. stack의 pop은 stack에서 가장 마지막 엘리먼트를
            # 뽑아오므로 현재 날짜에서 n번 건너뛴 숫자가 현재 index - last 가 되는 것이다.
            answer[last] = i - last

        # stack(index)이 없을 때, stack에 현재 index를 추가해준다. 여기서 index를 추가해주는 이유는 while문 위에서 추가해주면 stack[-1]이 결국엔 자기 자신(i)이 된다.
        stack.append(i)

    return answer

코드가 굉장히 짧은데 공부하느라 작성한 주석때문에 괜히 길어보인다.

 

가장 먼저, 이 풀이는 answer에 append하는게 아니라 모두 0일 때부터 시작해서, 각각 날짜를 바꿔주는 방식을 채택하고 있다.

answer = [0] * len(temperature)에서 확인할 수 있는데, 리스트 * 숫자를 해주면 리스트가 곱한 숫자만큼 늘어난다.

 

또, 다음 날짜로 넘어가는 부분을 index를 이용해서 구현하였는데, 이걸 위해 index도 필요하고 온도비교를 위해 value 값도 필요하다.

 

이때 필요한게 바로 enumerate()이다.

이 함수는 for문에서 index로 일일히 값을 가져오지 않고 for문 자체에서 index와 value를 뽑아낼 수 있게 해주는 함수이다.

매우 유용하니 잊지 말자.

 

 

이쯤되면 이제 익숙한 while stack and 원하는 조건 방식을 사용한다. 

가장 먼저, stack에 담긴 인덱스가 없으므로 stack.append(i)를 해준다.

 

다음 for문으로 넘어가면 이제 날씨를 비교하기 시작한다.

현재의 온도가 전 날의 온도 ( temperature[stack[-1]] )보다 높으면 while문에 들어가게 된다. 

 

last = stack.pop()

가장 먼저 stack에 담아 줬던 첫번째 날의 인덱스를 꺼내와서 last 변수에 담아준다.

 

answer[last] = i - last

answer의 last번째 인덱스에(이번 for문이 돌아가기 전 index가 last에 담겨있다.) 현재의 인덱스 - last 인덱스를 넣어준다.

그런데 왜 i에 last를 빼주는걸까?

while 조건에서 현재의 날씨가 전날의 날씨보다 낮은 경우 while문을 건너뛰고 stack에 계속 쌓아준다. stack의 pop은 stack에서 가장 마지막 엘리먼트를 뽑아오므로 현재 날짜에서 n번 건너뛴 숫자가 현재 index - last 가 되는 것이다.

 

위와 같은 과정을 반복해서 원하는 값을 answer에 전부 입력한 후 return하면 해결!

---

마치며

사실 이번 문제 정리는 대략 정신이 멍한 상태라서 주석에 작성해논 내용을 거의 그대로 가져다 썼다. 물론 내가 써논거지만 문제를 정리하면서 다시 공부하려는 목적이 큰데 역시 너무 늦게까지는 공부를 미루면 안되겠다.