739. Daily Temperatures

문제링크:https://leetcode.com/problems/daily-temperatures/

기온이 따뜻해질 때까지 필요한 날을 결과 배열로 반환한다. 이때 더 따뜻해지지 않는 경우 0으로 한다.

Solution

1. Reverse iteration with hashmap

언제 따뜻해지는지 알려면 미래의 데이터를 먼저 알아야한다. 이 점에서 뒤쪽부터 탐색하는 방식을 고려했다. i번째 기온을 봤을 때 미래의 기온 중에 자신보다 낮은 기온은 모두 지우고높은 기온 중 가장 낮은 기온이 위치한 index를 얻어서 i에 빼면 결과를 얻을 수 있다. 그리고 자신의 기온과 index를 추가하면 이후에도 자료를 사용할 수 있다. 이 때 미래의 기온과 index를 저장하는 것을 map을 이용해 구현해보았다.

Alogorithm

• result와 tempMap을 정의하고 뒤에서부터 탐색한다.
• 현재 기온 curTemp를 기준으로 tempMap에서 텍스트curTemp보다 낮은 값들은 모두 삭제한다.
• 그리고 curTemp보다 높은 값 중에 가장 작은 기온 lowest를 얻는다.
• lowest가 존재할 경우 i와 tempMap.get(lowest)의 차가 결과값이 된다.
• 존재하지 않는 경우 더 따뜻해지지 않기 때문에 0이 된다.
• tempMap에 curTemp값과 i를 추가한다.
• 위 과정을 맨 앞까지 반복해 결과 배열을 모두 얻는다.

var dailyTemperatures = function(temperatures) {
  // 뒤에서부터 탐색
  const result = new Array(temperatures.length);
  const tempMap = new Map();
  for (let i = temperatures.length - 1; i >= 0 ;i--) {
    // tempMap에 자신보다 높지만 가장 작은 key찾기
    const curTemp = temperatures[i];
    let lowest = Infinity;
    tempMap.forEach((val, key) => {
      if (key > curTemp) lowest = Math.min(lowest, key);
      else tempMap.delete(key);
    })
    if (lowest < Infinity) {
      result[i] = tempMap.get(lowest) - i;
    } 
    result[i] = lowest < Infinity ? tempMap.get(lowest) - i : 0;
    tempMap.set(curTemp, i);
  }
  return result;
};

시간복잡도는 n의 탐색과 1,2,3,...,n으로 늘어날 수 있는 tempMap의 사이즈에 따른 반복으로 총 O(n^2)가 된다. 공간복잡도는 tempMap에 따라 O(n)이 된다.
curTemp보다 낮은 기온이 전부 지워지게 되는데 이들은 더 높은 기온보다 최근에 생성된 데이터다. 즉 온도가 낮을수록 최근에 추가된 데이터로 모든 tempMap을 반복하지 않더라도 최근에 추가된 데이터 순으로 탐색하게 되면 가장 낮은 기온부터 탐색하게 된다는 특징이 있었다.

2. With stack

1번에서 발견한 tempMap의 특징을 잘 살릴 수 있는 stack을 통해 구현해보기로 했다. 결국 curTemp보다 같거나 낮은 기온은 pop을 통해 제외시킬 수 있고 처음만난 curTemp보다 높은 기온은 그 중에 가장 낮은 기온으로 뒤를 더 탐색하지 않고도 1번에서 쓴lowest를 판별할 수 있게 된다. 따라서 더욱 효율적인 방법으로 문제를 해결할 수 있다.

Algorithm

• result와 stack을 정의한다.
• 뒤에서부터 탐색하며 curTemp를 stack의 가장 윗값stack.at(-1)의 기온과 비교한다.
• curTemp보다 같거나 낮은 온도의 경우 pop()을 통해 제외시키는 것을 반복한다.
• 스택이 비어서 끝날 경우 result[i] = 0, 높은 기온이 존재할 경우 해당 index와 비교해 result[i]를 얻는다.
• stack에 [curTemp, i]를 push한다.
• 맨 앞까지 반복하면 result의 모든 결과를 얻을 수 있다.

var dailyTemperatures = function(temperatures) {
  // 뒤에서부터 탐색
  const result = new Array(temperatures.length);
  const stack = []; // [temp, index]
  for (let i = temperatures.length - 1; i >= 0 ;i--) {
    // stack에 자신보다 높은값이 남을때까지 pop
    const curTemp = temperatures[i]
    while (stack.length && stack.at(-1)[0] <= curTemp) {
      stack.pop();
    }
    // stack에 남은값이 없으면 0, 있으면 peek.index - i
    result[i] = stack.length ? stack.at(-1)[1] - i : 0;
    stack.push([curTemp, i]);
  }
  return result;
};

시간복잡도와 공간복잡도 모두 1번과 같다. 하지만 최악의 경우가 아니라면 map을 모두 탐색하는 것에 비해서 stack에서 큰 값이 나올때까지만 탐색하는 것은 pruning이 되기 때문에 더 효율적이라고 할 수 있다.