leecode[739] - Daily Temperatures (Medium)

1. 문제 링크:

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

Daily Temperatures - LeetCode

 

2. 문제

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

주어진 배열의 숫자는 일별 온도입니다. 며칠이 지나면 더 따뜻한 날이 오는지 answer[i] 에 저장해서 리턴해주세요.
만약 더 따뜻한 날이 없을 경우에는 answer[i] ==0 을 넣으면 됩니다.

3. example

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Input: temperatures = [30,60,90]
Output: [1,1,0]

 

4. 주의할 점

며칠이 지나면 오늘보다 더 따뜻한 날이 오는지 에 관한 것이다.
오늘보다 1도라도 높은 날이 오면 그날이 오늘부터 며칠 후 인지를 알아야 한다.
리트코드는 이렇게 좀... 한 번씩 문제를 어렵게 만든다....

 

5. 풀이

일단은 간단하게... 그대로 탐색을 한다
아래 풀이로는 Time Limit Exceeded

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = []
        for i, val1 in enumerate(temperatures):
            ret = 0
            if len(temperatures[i:]) <= 1:
                answer.append(ret)
                continue
            max_val = max(temperatures[i:])
            if val1 < max_val:
                for j, val2 in enumerate(temperatures[i+1:]):
                    if val1 < val2:
                        ret = j+1
                        break
            answer.append(ret)
        return answer

 

더 나은 방법이 없어서 컨닝..
Discuss 에 가면 다른 사람들의 코드를 볼 수 있다.
(돈을 내면 Solution을 볼 수는 있다....)

이걸로 일단 제출!

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        len_temp = len(temperatures)
        answer = [0] * len_temp
        stack = []
        for i in range(len_temp):
            while stack and temperatures[stack[-1]] < temperatures[i]:
                top_stack = stack.pop()
                answer[top_stack] = i - top_stack
            stack.append(i)
        return answer

코드를 봐도 이해가 안.... 돼서 시뮬레이션

temp = [30, 60, 90]

i =0
1. stack 이 없으므로 stack 에 0 추가

i =1
1. stack 이 있고  temp[stack[-1]] = 30 < temp[1]=60
2. top_statck = 0
3. anwer[top_stack] = i - top_stack = 1
4.stack 이 없으므로 sttack 에 1추가

i=2
1. stakc 이 있고 temp[stack[-1]] = 60 < temp[2]=90
2. top_stack = 1
3. anwer[1] = 2-1(top_stack) =1

answer = [1,1,0]

내 코드와 다른 점은
1. answer 배열에서 append를 하지 않고 미리 0을 채워놓았다는 것
2. stack자료구조 이용
3. for 문에서 현재와 미래의 값을 사용하지 않고 stack에 과거의 값을 넣어둔 다음 현재 값과 비교했다.

조금 더 예외처리가 추가된 버전

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        if not temperatures:
            return []
        n = len(temperatures)
        if n == 1:
            return [0]
        days = [0]*n
        stack = []
        for i,t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                j = stack.pop()
                days[j] = i-j
            stack.append(i)
        
        return days

컨닝해도 괜찮다.
컨닝한 것을 내 것으로 만들고 다음에 비슷한 문제가 나왔을 때 이용할 수 있을 만큼
내 것으로 만들면 된다.