739. Daily Temperatures ★★★★★ 이해안감!

739. Daily Temperatures

 

❌ 문제점 요약

• temperatures 배열은 정렬되어 있지 않기 때문에, 이진 탐색 (binary search)을 사용할 수 없습니다.
• dfs(i+1, val) 함수는 i+1 ~ 끝까지 중 val보다 큰 수를 이진 탐색으로 찾지만, 이건 정렬된 배열에서만 유효합니다.
• 따라서 현재 접근 방식은 잘못된 가정에 기반한 것입니다.

---

✅ 올바른 풀이: Stack (O(n))

가장 적절한 방식은 스택을 이용한 역방향 탐색입니다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = [0] * n
        stack = []  # 인덱스를 저장

        for i in range(n - 1, -1, -1):  # 역순으로 탐색
            # 현재 온도보다 작거나 같은 온도는 필요 없음 (stack에서 제거)
            while stack and temperatures[i] >= temperatures[stack[-1]]:
                stack.pop()

            if stack:
                res[i] = stack[-1] - i  # 다음 더 따뜻한 날까지의 거리

            stack.append(i)  # 현재 인덱스를 stack에 저장

        return res

---

🔍 예시

입력: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
출력: [1, 1, 4, 2, 1, 1, 0, 0]

---

📌 시간 복잡도

• 스택 풀이는 각 인덱스를 최대 한 번 push/pop → O(n)
• 이진 탐색 방식은 O(n log n)처럼 보이지만, 정렬되지 않은 배열에서는 잘못된 로직입니다.

https://youtu.be/cTBiBSnjO3c?si=oBmddqECHrmZhNjw