Daily Temperatures

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.

매일의 온도를 나타내는 int형 배열 temperatures가 주어진다. answer 배열의 원소 answer[i]는 i번째 날의 온도보다 더 따뜻해지기까지 며칠을 기다려야하는지 나타낸다. 만약 더 따뜻해지는 날이 없다면 answer[i] == 0 이다. answer배열을 반환하는 함수를 구현하시오

예시 1:
 
입력 -> 온도 = [73,74,75,71,69,72,76,73]
출력: [1,1,4,2,1,1,0,0]

예시 2:
 
입력 -> 온도 = [30,40,50,60]
출력: [1,1,1,0]

예시 3:
 
입력 -> 온도 = [30,60,90]
출력: [1,1,0]

제약사항:
 
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

문제 해결을 위한 아이디어

우선 제약 사항을 보면 10^5로 n^2으로 풀면 안된다는 걸 알 수 있따.

그래서 첨에는 완전 탐색으로 풀면 되지 않을까 고민했는데 다른 방법을 떠올려야 했다.

괄호 유효성 문제와 비슷하다고 생각해보기.

특정 조건에서만 반응한다. 주어진 숫자보다 큰 숫자를 가지는 것만 의미를 가진다.

Solution

파이썬

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        ans = [0] * len(temperatures)
        stack = []
        for cur_day, cur_temp in enumerate(temperatures):
            while stack and stack[-1][1] < cur_temp:
                prev_day, _= stack.pop()
                ans[prev_day] = cur_day - prev_day
            stack.append((cur_day, cur_temp))
        return ans

JS로 풀어보기

function dailyTemperatures(temperatures) {
  const ans = Array(temperatures.length).fill(0);
  const stack = [];
  temperatures.forEach((temp, day) => {
    while (stack.length !== 0 && stack[stack.length - 1].temp < temp) {
      const { day: prev_day } = stack.pop();
      ans[prev_day] = day - prev_day;
    }
    stack.push({ day, temp });
  });
  return ans;
}

Browser History Greedy