Daily Temperatures - leetcode(739)

llama·2022년 3월 14일

leetcode 알고리즘

알고리즘

목록 보기

3/16

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.
=> 일별 온도를 나타내는 정수 배열에서 현재 날보다 더 따뜻한 날이 되는날까지 걸리는 날을 배열로 만들고, 만약 가능한 날이 없다면 0을 넣어서 반환한다.

Stack 이란

LIFO(Last In First Out)로 후입선출이라는 구조적 특징을 가져서 한쪽 끝에서만 자료를 넣고 빼는 자료구조이고, 데이터를 넣은 순서를 이용해야될 경우 필요하다.

Solution

preInput = [73, 74, 75, 71, 69, 72, 76, 73]

class Solution:
    def dailyTemperatures(self, temperatures):
        answer = [0] * len(temperatures)
        stack = []
        
		# index를 요일로 이용한다.
        for today_day, today_temp in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < today_temp:
            	# stack의 요일을 빼고, 오늘날과 비교해 걸린 시간을 답에 넣어준다.
                past_day = stack.pop()
                answer[past_day] = today_day - past_day
            stack.append(today_day)

        return answer

sol = Solution()

print(sol.dailyTemperatures(preInput))
# >>> [1, 1, 4, 2, 1, 1, 0, 0]

📌 코드 풀이

요구조건에 가능한 날이 없다면 0을 반환하여야 하기 때문에 답을 [0] * len(temp)를 곱해서 만들어 둔다.

과거의 날과 오늘의 온도를 비교하여야 하기 때문에 데이터를 쌓아둘 스택을 배열로 선언해둔다.

enumerate(temp)를 이용하여 for문을 돌때 index를 요일로 이용할 수 있게 만든다.

for문안에서 while문을 도는데 stack이 있고, stack에 담긴 요일의 온도가 오늘의 온도보다 낮다면 오늘이 더 따뜻날이기 때문에 와일문이 돌게되고 온도를 비교한 요일을 pop()을 이용해 변수에 담아둔다.

answer[past_day]로 과거의 요일에 오늘날 - 과거날로 따뜻해지기 까지 걸린 요일을 넣어준다.

stack이 없거나 과거날의 온도가 오늘보다 높다면 와일문을 빠져나오고, 오늘(index)을 stack에 넣어준다.