[Leetcode 아주 상세한 문제풀이] 739. Daily Temperatures - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 739번 문제 Daily Temperatures 다.

우선 문제를 살펴보자.

 

리트코드 739번 문제 Daily Temperatures 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

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.

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]
 
Constraints:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

 

 

문제 설명

문제를 간략히 살펴보자. 매일의 온도를 나타내는 배열 temperatures가 주어진다. 이 배열은 인덱스 순서대로 매일의 날씨를 나타낸다. 이때 해당 날짜로 부터 날이 더 따뜻한 (온도가 더 높은) 날짜가 며칠만에 오는지 알아보라는 것이다.

예를 들어 매일의 온도가 temperatures = [30,40,50,60]로 주어졌다고 생각해 보자. 첫번째날 온도는 30도 이기 때문에 하루만 있으면 40도가 되어 더 따뜻한 날이 된다. 두번째날 온도는 40도 이기 때문에 또 하루만 있으면 50도가 되어 더 따뜻한 날이 된다. 이런식으로 '며칠을 기다려야 오늘보다 더 따뜻한 날이 되나'를 계산해보면 [1,1,1,0]과 같은 결과를 얻을 수 있다.

문제를 이해하기 어렵지 않으므로 곧바로 문제를 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해서 우리는 stack을 이용할 것이다.

핵심 아이디어는 주어진 temperatures 배열을 탐색하는데 stack을 이용하여 '다음 따뜻한 날'을 찾는 것이다.

구체적으로 어떻게 알고리즘을 짜야 하는지 살펴보자.

문제 예시 1번

우선 정답을 저장할 배열 (answer)과 wailing list를 하나 만들어준다.

만약 temperatures가 [73,74,75,71,69,72,76,73]와 같이 주어진 경우 다음과 같이 진행된다.

1) Day 0: waiting list=[]

2) Day 1: 전날보다 온도가 높다. 하루만에 온도가 높아졌으니 answer=[1]이 된다. 다음 비교를 위해 Day 1을 waiting list에 넣어준다. waiting list=[1]

3) Day 2: 전날보다 온도가 높다. 하루만에 온도가 높아졌으니 answer=[1, 1]이 된다. 더 따뜻한 날을 찾았으므로 waiting list를 업데이트 해준다. waiting list=[2]

4) Day 3: 전날보다 온도가 낮다. 추후 비교를 위해 Day 3를 waiting list에 넣어준다. waiting list = [2,3]

5) Day 4: 전날보다 온도가 낮다. 추후 비교를 위해 Day 4를 waiting list에 넣어준다. waiting list = [2,3,4]

6) Day 5: 전날보다 온도가 높다. 또한 waiting list에 있는 Day 3 & 4 온도와 비교해도 높다. 따라서 answer=[1, 1, ?, 2, 1]이 된다. 그리고 더 따뜻한 날을 찾았으므로 waiting list에서 Day 3 & 4를 제거하고 Day 5를 넣어준다. waiting list =[2, 5]

7) Day 6: 전날보다도 온도가 높고 waiting list에 있는 Day 2 & 5보다도 높도가 높다. 따라서 answer=[1, 1, 4, 2, 1, 1]로 업데이트 한다. 그리고 waiting list에는 Day 6만 남아있다. waiting list=[6]

8) Day 7: 전날보다 온도가 낮다. 추후 비교를 위해 Day 7를 waiting list에 넣어준다. waiting list = [6,7]

Day 7 까지 탐색을 마친 후 waiting list에 Day 6 & 7이 남아있다. 즉, 이 두 날보다는 더 높은 온도인 날이 없다는 뜻이다. 따라서 answer를 업데이트해 최종적으로 [1, 1, 4, 2, 1, 1, 0, 0]을 얻을 수 있다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

온도를 입력받을 함수를 정의해 준다. (line 1)

Answer 배열을 입력받은 temperatures 길이와 동일하게 만들어 주고 0으로 초기화 해준다. (line 2-3)

그리고 더 따뜻한 날을 추척하기 위한 stack을 하나 만들어 준다. (line 4)

이제 temperatures 배열을 for loop를 이용해 탐색할 것인데 이때 인덱스와 값을 가져온다. (line 6)

만약 stack안에 값이 존재하고 현재 온도가 stack이 가장 뒤에 있는 온도보다 높다면 (line 7)

Stack에서 그 element를 pop으로 빼내고 그에 해당하는 answer의 인덱스에 현재 탐색하고 있는 날과 그 빼낸 인덱스 차이를 넣어준다. (line 8-9)

이 부분이 헷갈린다면 문제 접근법에서 Day 5를 다시 살펴보면 된다.

Day 5에서 waiting list = [2,3,4]이기 때문에 4일차에 해당하는 answer 값은 5-4로 1이 된다.

즉, Day 4에서 Day 5까지 하루만에 온도가 더 높아진다는 것이다.

만약 stack안에 값이 존재하지 않거나 혹은 현재 온도가 stack이 가장 뒤에 있는 온도보다 높지 않다면 다음 탐색을 위하여 해당 인덱스 값을 stack에 쌓아둔다. (line 10)

이 과정을 모두 마치고 나면 answer 안에 우리가 구하고자 하는 값이 있으므로 이것을 리턴하고 종료한다. (line 12)

 

 

문제 풀이 코드

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []  # This will store indices of the temperatures array
 
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index
        stack.append(i)
 
    return answer
 
# Test the function with the provided examples
print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))  # [1, 1, 4, 2, 1, 1, 0, 0]
print(dailyTemperatures([30, 40, 50, 60]))                  # [1, 1, 1, 0]
print(dailyTemperatures([30, 60, 90]))                      # [1, 1, 0]
 

 

 

739. Daily Temperatures