leetcode 739. Daily Temperatures 일일 온도 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

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

Daily Temperatures - LeetCode

입력: 그날의 온도가 입력되어있는 리스트

출력: 그날의 온도보다 더 높은 온도를 기록한 날과의 날짜 차이를 입력한 리스트

 

문제 요약: [3,4,5] 가 input이라면, index 0자리는 3 index 1dml 4가 더 크므로 1-0 = 1, index 1자리는 4, index 2자리는 5로 더 크므로 2-1=1 index 2자리의 5는 마지막이므로 0이 와서 output은 [1,1,0] 이 와야 한다.

 

이 문제는 책의 더 앞부분에 나왔던 리트코드 42번 문제와 유사한데, 그때도 어려워서 잘 풀지 못했던 문제였다.

이번에도 문제를 보고 바로 풀이방법을 생각해내지는 못했고, 책을 참고하여 문제를 풀었다.

 

유의 사항: 마지막에 와서 뒤에 더 큰 값이 없는 애들도 자기 인덱스에 0을 채워넣어줘야 한다.

생각 과정

output 리스트에 들어가는 값은 인덱스의 차이이다.

그래서 인덱스를 넣는 리스트를 따로 만들어줘야 한다.

그리고 마지막에 와서 뒤에 더 큰 값이 없는 애들도 자기 인덱스에 0을 채워넣어줘야 한다.

파이썬의 enumerate()은 리스트의 index와 value를 tuple로 반환해주니까 이것을 활용해서 value를 비교하고, index의 차를 새로운 리스트에 넣어준다.

풀이

 

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        lst= [0]*len(temperatures)
        for key, val in enumerate(temperatures):
    #stack의 제일 마지막 key값에 해당하는 온도보다 새로 들어온 온도가 더 높으면, 그 현재의 key 와 그 마지막 key의 차를 정답 리스트에 넣는다. 
            while stack and val > temperatures[stack[-1]]:
                last = stack.pop()
                lst[last] = key - last
            #stack에는 새 key 값을 넣는다.    
            stack.append(key)
        return lst