[LeetCode 해석 및 풀이] 739. Daily Temperatures

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.

 

한글

일일 기온을 나타내는 정수 배열 temperatures가 주어지면, answer[i]가 i번째 날이 더 따뜻하진 날이 되기까지 기다려야 하는 일 수인 배열 answer를 반환하세요. 만약 가능한 미래 일수가 없다면 대신 answer[i] == 0을 하세요.

 

제한조건

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

 

입출력 예

입력	출력
temperatures = [73,74,75,71,69,72,76,73]	[1,1,4,2,1,1,0,0]
temperatures = [30,40,50,60]	[1,1,1,0]
temperatures = [30,60,90]	[1,1,0]

 

 

해답 및 해설

파이썬 (Python)

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

        for cur_i, cur_temp in enumerate(temperatures):
            while 1:
                if len(stack) == 0:
                    stack.append((cur_i, cur_temp))
                    break
                
                last_i, last_temp = stack[-1]

                if last_temp >= cur_temp:
                    stack.append((cur_i, cur_temp))
                    break
                
                stack.pop()
                answer[last_i] = cur_i - last_i

        return answer

처음에는 인덱스와 온도를 stack에 넣고, 기온이 stack에 있는 요소들보다 올라간다면 stack의 요소를 빼고 해당 요소의 인덱스에 날짜 차이를 넣어준다. 만약 기온이 내려간다면 스택에 요소를 넣는다. 이 과정을 기온 배열 전체를 반복문들 돌려 해준다.

 

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

        for cur_i in range(len(temperatures)):
            while stack and temperatures[cur_i] > temperatures[stack[-1]]:
                last_i = stack.pop()
                answer[last_i] = cur_i - last_i
            stack.append(cur_i)

        return answer

생각해보니 온도까지 stack에 넣을 필요는 없을거 같아서 다음과 같이 푸는게 더 나을듯 싶다.