[leetCode/JS] 739. Daily Temperatures

난이도 [ 🤔 ] Medium

 

 

문제 설명

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.

일일 온도가 입력된 배열에서 더 따듯해지는 날까지의 일 수의 배열을 반환하면된다. 없으면 0으로 리턴한다.

 

 

 

입출력 예

Example 1:

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

 

Example 2:

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

 

Example 3:

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

 

 

 

 

Constraints

• 1 <= temperatures.length <= 105
• 30 <= temperatures\[i\] <= 100

 

---

 

내 솔루션

• 그냥 순회해서 index 찾아서 index 리턴해서 끝낼라 했는데...
• Time Limit에 걸리고 beats 5%로 엄청 느렸다.

// Time Limit
var dailyTemperatures = function(temperatures) {
  const answer = [];
  for(let i = 0; i < temperatures.length; i++) {
    const index = temperatures.slice(i+1).findIndex(t => temperatures[i] < t) + 1;
    answer.push(index);
  }
  return answer;
};


// Runtime 8683ms, beats 5%
var dailyTemperatures = function(temperatures) {
  const answer = [];
  for(let i = 0; i < temperatures.length; i++) {
    for(let j = i; j < temperatures.length; j++) {
      if(temperatures[i] < temperatures[j]) {
        answer.push(j-i);
        break;
      } else if ( j === temperatures.length - 1){
        answer.push(0);
      }
    }
  }
  return answer;
};

 

 

• 결국엔 검색시작! 2포인트 서치나 스택에 쌓는 방법을 사용했더라..
• 이해하기 쉬운건 스택을 이용한 탐색인데, 현재의 인덱스를 쌓아두고
• 가장 최근에 쌓인 온도보다 높은 온도가 나오면 스택에 꺼내고 그 차이를 계산에서 입력하는 방식이다.
• 말로는 어렵지만 코드를 보면 쉬웠다. 쥐엔장

var dailyTemperatures = function(temperatures) {
  const answer = Array(temperatures.length).fill(0);
  const stack = [];
  
  for(let i = 0; i < temperatures.length; i++) {
    let top = stack[stack.length-1];

    while(stack.length && temperatures[top] < temperatures[i]) {
      const idx = stack.pop();
      answer[idx] = i - idx;
      top = stack[stack.length-1];
    }
    stack.push(i);
  }
  return answer;
};

 

감상평

• 이보다 더 느리게 할 수 있을까?
• 다했다~ 싶을 때, 느려서 빠꾸먹으면 진짜 한숨이 ㅋㅋ