Daily Temperatures

문제 번호, 이름: 739. Daily Temperatures

문제 링크: https://leetcode.com/problems/daily-temperatures/description/

날짜: 2024/06/23

상태: 완료

 

이 문제를 고른 이유

문제 제목이 마음에 들어서 골라봤다

문제 보고 처음 든 생각

화씨 쓰네;

방금 전에 sliding window + deque 적용해야 하는 문제 공부 열심히 해놨더니 와 대박;; 바로 적용할 수 있는 문제를 골랐다

 

풀이 v1

• 소요 시간 15분

from collections import deque


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        len_temperature = len(temperatures)
        idx = len_temperature - 1
        answer = [0 for _ in range(len_temperature)]
        temperatures_increasing_order = deque()
        temperatures_increasing_order.append((temperatures[idx], idx))

        idx -= 1
        while idx >= 0:
            while temperatures_increasing_order and temperatures[idx] >= temperatures_increasing_order[0][0]:
                temperatures_increasing_order.popleft()

            if temperatures_increasing_order:
                answer[idx] = temperatures_increasing_order[0][1] - idx
            temperatures_increasing_order.appendleft((temperatures[idx], idx))
            idx -= 1

        return answer

 

• array를 뒤에서부터 읽어가며 deque에 저장한다.
• 앞쪽에 등장한 온도가 뒤쪽에 등장한 온도보다 높다면 이제 뒤쪽에 등장한 낮은 온도는 저장할 필요가 없어진다.
• deque에는 결국 나의 idx보다 오른쪽에서 등장한 숫자 중에 decresing order를 발생시키는 것을 다 제외한 increasing order 숫자만 남아 있다. 그래서 나보다 오른쪽에 등장했으면서 나보다 큰 숫자를 찾기 위해 deque를 pop시켜가며 확인을 한다 

풀이 v2

• 소요 시간 -

# if v2 exists

 

 

이 문제를 풀고 얻은 것

• 아까 문제 풀며 공부한것 적용

메모

• 사실 deque에 left쪽에 append, pop해도 되고 right쪽에 append, pop 해도 되고, 그러니 deque를 꼭 쓸 필요도 없긴 했다. deque는 left에 append/pop 하는게 빠른지 right쪽에 하는게 빠른지만 잠깐 알아보았다.
  똑같다고 한다? 오.. 똑같이 O(1)