leetcode 739. Daily Temperatures 풀이

문제 : int로 이루어진 list가 주어질때, 각 인덱스는 날짜, 원소는 온도를 나타낸다. 각 날짜의 날씨보다 따뜻한 날씨가 되는 날수를 원소로 갖는 list를 반환하라

Follow up :

 

아이디어 : V 자 형으로 계속 기온이 떨어지다가 올라가게 된다면, 최초의 날짜의 값을 추적하기 용이한 자료구조형을 사용해야할 것이다. 따라서 stack을 사용하여 (인덱스, 온도값) 을 저장하여 인덱스를 이동할때 stack의 top의 온도와 비교하여 더 높으면 pop을 하는 것을 반복한다. pop한 원소의 index와 현재 index를 비교하여 날짜를 계산한다.

 

코드 :

 

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        s = []
        ans = [0 for l in range(len(T))]
        for idx in range(len(T)):
            if not s:
                s.append((idx, T[idx]))
            else:
                while s:
                    if s[-1][1] < T[idx]:
                        i, temp = s.pop()
                        ans[i] = idx-i
                    else:
                        break
                s.append((idx, T[idx]))
        return ans

 

학습 포인트 : 상황에 따라 queue를 사용할지 stack을 사용할지 조금 보이는거같다. 조금 더 쉽게 풀 수 있도록 노력해야겠다.

 

출처 : leetcode.com/problems/daily-temperatures/