[알고리즘] Leetcode-daily-temperatures 파이썬 문제풀이

문제 링크

문제

temperatures라는 기온이 담긴 list를 입력 받아서 몇일 후에 해당 기온보다 높은 기온이 오는지를 list로 출력하는 문제이다. Stack을 사용하는 문제 유형 중 하나이다.

입출력 예시

조건

temperatures의 길이가 시간복잡도에 직접 영향을 미치는데, 최대가 10의 5승이기 때문에 O(n^2)을 사용하면 시간초과가 나기 때문에 그 이하의 시간복잡도를 가진 풀이방법을 찾아야 한다. 온도 하나하나의 크기는 시간복잡도에 영향을 미치지 않기 때문에 패스

풀이

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

Stack을 활용하는 대표 유형 중 하나이기 때문에 Stack을 사용해주었다.
앞의 기온보다 높은 기온이 온다면 앞의 기온들의 인덱스를 찾아가서 몇일이나 지났는지를 넣어줘야하기 때문에 인덱스 값을 함께 적어줘야 한다. 그래서 for문과 temperatures에 enumerate를 사용해서 인덱스를 cur_day, 기온을 cur_temp로 반복하게 해주었다.
만약 stack에 값이 존재하고, 현재 꺼낸 cur_temp가 stack의 top 온도보다 높다면 이전 날들보다 높은 온도가 온것이기 때문에 계산해서 해당 index에 얼마나 지났는지 날짜를 넣어주도록 했다. 만약 cur_temp가 top 온도보다 더 낮거나 같다면 아직 이전 날 보다 기온이 높은 날이 오지 않은 것이므로 stack에 cur_day, cur_temp를 넣어주도록 했다.
만약 영영 기온이 높은 날이 오지 않더라도 처음에 ans의 값들을 다 0으로 초기화해놨기 때문에 그대로 출력되면 정답이 된다.