Leetcode 739. Daily Temperatures - 자바스크립트

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

1. 문제설명

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.

Number형의 인자로 구성된 온도배열이 주어졌을 때, i번째 온도는 몇 일이 지나야 더 따뜻한 온도의 인자를 받는지 나타내는 문제. 즉, 현재 주어진 온도가 몇일이 지나야 더 높은 온도를 만나는지 그 값을 배열로 나타내는 문제이다. 만약 배열이 끝날때까지 더 따뜻한 날을 못만나면 0을 반환.

2. 풀이

N이 최대 10^5 이므로 매일매일을 다른 날짜의 온도들과 비교할 수 없다. 예를들어

for (let i=0; i<N; i++) {
	for (let j=i+1; j < N; j++) {
      if (temperature[i] < temperature[j])
        ....
}

이런식으로 구성하면 시간효율이 좋지 못하다. 그래서 stack을 사용했다.

모든 값은 stack에 (온도, 날짜) 형식으로 push한다. stack에 값이 들어있고 현재온도가 stack의 마지막 인덱스의 온도보다 높다면 pop하여 값을 입력한다. 반복적으로 수행하며 그렇지 않으면 break시킨다. 왜냐하면 stack은 항상 오름차순으로 저장되고 현재온도보다 큰 stack값을 만나면 더이상 반복문을 돌릴 이유가 없기 때문이다.

릿코드의 예시를 보자. temperatures = [73,74,75,71,69,72,76,73]

1. 처음에는 73값이 들어온다. 그리고 stack = [73]
2. 74. stack의 마지막 값은 현재값보다 작다. pop하고 stack 쌓기. stack = [74]
3. 75. stack의 마지막 값이 현재값보다 작다. pop하고 stack 쌓기. stack = [75]
4. 71. stack의 마지막 값이 현재값보다 크다. stack 쌓기만. stack = [75, 71]
5. 69. stack의 마지막 값이 현재값보다 크다. stack 쌓기만. stack = [75, 71, 69]
6. 72. stack의 마지막 값이 현재값보다 작다. 반복으로 pop하고 stack 쌓기. stack = [75, 72]
7. 계속 이런식으로 반복하기...

3. 정답코드

const dailyTemperatures = (temperatures) => {
  	// 배열 초기화
    const answer = Array.from({length: temperatures.length}, () => 0);
    const stack = [];
    temperatures.forEach((temperature, day) => {
      	// stack의 값이 들어있고, 현재온도가 stack의 마지막 온도보다 클 때, pop하고 정답입력.
        while (stack.length && temperature > stack[stack.length-1][0]) {
            const [__, prevDay] = stack.pop();
            answer[prevDay] = day - prevDay;
        }
        
        stack.push([temperature, day]);
    })
    return answer;
};