[LeetCode] 739. Daily Temperatures 일일 온도

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

739번 Daily Temperatures는 매일의 온도를 리스트를 받아서 해당 일자 기준, 며칠을 더 따뜻한 날씨를 기다려야 하는 지 출력하는 문제이다.

Example

 

 

# 풀이방법 1  - 책 풀이 참고

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        result = [0] * len(temperatures)
        stack = []
        
        # (for문으로 temperatures 한 번만 순회하면서, stack에 인덱스를 저장)
        for i, t in enumerate(temperatures) :
            
            # stack에서 값을 꺼내어, 현재 온도 보다 낮은 것이 있다면 pop하여 result에 날짜 차이를 저장
            while stack and t > temperatures[stack[-1]] : 
                last = stack.pop()
                result[last] = i - last
            
            stack.append(i)
            
        return result

| 아이디어  | 

스택에 현재의 인덱스를 저장해두다가, 이전과 온도가 높아지는 시점에 스택에서 값을 꺼내어 값을 비교한다. 

조건을 만족한다면, pop하여 result 배열의 해당 인덱스에 날짜 차이를 저장한다. 

- 스택에는 모든 인덱스가 append된다.  

 

 

| 핵심 |

# stack에서 값을 꺼내어, 현재 온도 보다 낮은 것이 있다면 pop하여 result에 날짜 차이를 저장
            while stack and t > temperatures[stack[-1]] : 
                last = stack.pop()
                result[last] = i - last
            
            stack.append(i)

 

 

# 결과  

내 힘으로 온전히 풀지 못하여 아쉬운 문제이다. 2회독 때는 꼭 혼자 힘으로 풀 수 있도록 해야겠다.