[leetcode 2024/02/06] 739. Daily Temperatures

https://leetcode.com/problems/daily-temperatures/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

처음에 brute force로 접근 했다가 시간 초과가 되었다.

결국 다른 대안을 생각해내지 못해서, chat GPT의 도움을 받아서 문제를 이해하게 되었다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        days = [0]*len(temperatures)
        for i in range(0, len(temperatures), 1):
            day = 0
            for k in range(i, len(temperatures),1):
                if(temperatures[i] < temperatures[k]):
                    days[i] = day
                    break
                else:
                    day +=1
        return days

시간 초과가 난 코드는 위와 같다. 시간 복잡도가 O(n^2) 이다.

 

이해한 접근 방법은 다음과 같다.

일단 for 문으로 temperatures를 돌린다.

또한 stack = [] 또한 선언해준다.

 

1) stack이 비어있지 않거나

2) temperatures[stack[-1]] < temperatures[i]

인 경우,  

temp = stack.pop() # 가장 나중에 저장한 것의 index
day = i - temp # 현재 index와 stack에 저장해두었던 index의 차를 통해서, 걸린 날 계산
result[temp] = day #result에 저장

를 통해서 날씨가 따뜻해지기까지 걸린 날을 계산해주었다.

 

이는 while 문을 돌려서, 이전에 stack에 저장해두었던, 날들까지 다시 비교해주었다.

 

10 9 7 11 을 예로 들어보자.

10 의 경우, stack 이 비었기 때문에 stack에 저장.

9의 경우, 10 < 9 를 만족하지 못하기 때문에, stack에 저장

7의 경우, 9 < 7 을 만족하지 못하기 때문에, stack에 저장

 

즉, 날씨가 점점 추워졌기 때문에, 7에 대해서 10< 7 을 통해 비교해줄 필요가 없다.

추워지기만 했기 때문에, 10 보다 온도가 높을 수 없기 때문이다.

 

하지만, 11이 나왔을 때, 

7 < 11 이고, 11의 경우 10, 9 보다 온도가 높을 가능성이 있기 때문에 (온도가 따뜻해졌기에), while 문을 돌려서

조건문이 true라면 index끼리의 차를 통해서, 날씨가 따뜻해지기까지 걸린 날들을 계산해 주었다. 

 

이번 문제에 대해서 조금 아쉬움이 남지만, 다음에는 이런 비슷한 문제가 나왔을 때 조금 더 가까이 다가갈 수 있을 것이라 생각한다.

 

2. 코드

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        result = [0]*len(temperatures)

        for i in range(0, len(temperatures), 1):

            while stack!=[] and (temperatures[stack[-1]]<temperatures[i]):
                temp = stack.pop()
                day = i-temp
                result[temp] = day
            stack.append(i)
        return result