03/18 알고리즘 문제풀이 - 739. Daily Temperatures (Leetcode)

문제

• Leetcode 알고리즘 문제
• 739. Daily Temperatures (Medium)
• 문제 내용 : [링크]
  

내가 작성한 코드

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        ans = [0] * len(temperatures)
        stack = []
        
        for day, temp in enumerate(temperatures):
            while stack and stack[-1][1] < temp:
                prev_day = stack.pop()[0]
                ans[prev_day] = day - prev_day
            stack.append((day, temp))
        return ans

• temperatures 리스트 안에 있는 일자별 온도를 기준으로, 해당 온도보다 더 높은 온도값을 가지는 날을 맞이할 때까지 걸린 일수를 계산하는 문제이다.

• stack을 사용하여, 그 날 온도보다 더 온도가 높은 날이 나타날 때까지 stack에 저장한다.

• 만약 더 높은 온도를 가진 날이 나타날 경우, stack에 저장된 정보를 통해 prev_day 값을 구하고 ans에 업데이트 해준다.

• 즉, for문을 돌면서 특정 일자(i)의 온도를 기준으로, stack에 담겨있던 일자와 온도들을 비교해서 특정 일자의 온도가 크면 ans에 걸린 기간(day - prev_day)을 업데이트하고 pop() 해준다.

• 모든 pop()이 다 끝나면, i번째 일자와 온도를 stack에 담아준다.

⭐

1. 왜 stack 사용? - 가장 최근일자를 기준으로 차례대로 계산해야 하기 때문에.

2. stack 사용하다가 중간 큰 값에 막혀서 그 아래 있는 온도 못빠져나오면 어떡함? - 그럴일 없음. 그 중간 큰 값이 append 되기 전에 pop 되었을거임.