22. Daily Temperatures

🎯 leetcode - 739. Daily Temperatures

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 23번 문제

📌 날짜

2020.01.29

📌 시도 횟수

3 try / Failed

💡 실패 Code

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        arr = []
        for i in range(len(T)):
            exist = False
            count = 0
            for j in range(i + 1, len(T)):
                count += 1
                if T[i] < T[j]:
                    exist = True
                    arr.append(count)
                    break
            if not exist:
                arr.append(0)

        return arr

💡 문제 해결 방법

- 브루트포스 방법을 이용하여 풀었다.

💡 새롭게 알게 된 점

- 

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 런타임 에러가 발생했다!
- O(n)에 풀 수 있는 방법을 생각해야 한다.

---

😉 다른 풀이

📌 하나. 스택 이용하기

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        answer = [0] * len(T)
        stack = []
        for i, cur in enumerate(T):
            while stack and cur > T[stack[-1]]:
                last = stack.pop()
                answer[last] = i - last
            stack.append(i)
        return answer

💯 문제 풀이 과정

• 위의 코드를 이해하기 위해 예시로 T = [55, 38, 53, 81, 61]를 가져왔다.
  
• i가 1씩 늘어날수록 위의 코드는 아래과 같은 과정을 거친다.
• 참고로 만약 높은 온도가 나오지 않아 스택에서 비워지지 못한 값들에 대해서는 0이 출력되어야 하므로, answer 리스트는 처음부터 디폴트로 0의 값을 len(T) 만큼 할당해 주었다.

▶ 여전히 이해가 어렵다면 🌵여기를 눌러🌵 천천히 이해해보자

💡 새롭게 알게 된 점 / 느낀점

- stack의 원리를 실제로 잘 사용한 문제인 것 같다.
- 아직은 좀 낮선 방식의 풀이인 것 같다ㅠㅠ

---

추가 설명(Stack의 원리 + 문제 해결 팁 이용)😵

• 나중에 이 문제를 다시 풀 때 어떻게 하면 기억에 빡! 남을 수 있을까 고민하다가 아래의 예시를 한번 만들어 보었다.
• 스택의 원리 + 위의 문제 해결 팁을 스토리텔링 식으로 이해하기 쉽도록 한번 만들어봤다.
• 이렇게 하면 기억에 잘 남겠지?🥺