[LeetCode] Daily Temperatures

https://leetcode.com/problems/daily-temperatures/description/?envType=study-plan-v2&envId=leetcode-75

 

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.

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

---

일별로 기온이 기록된 배열이 주어지고,

i번째 날보다 따뜻한 날이 되려면 최소 며칠을 기다려야 하는지를 i번째에 기록한 새로운 배열 answer를 리턴하는 문제다.

 

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    // 더 따뜻한 날이 될때까지 걸리는 일수를 리턴, 같은 날만 있거나 없으면 0
    const stack = [];
    for(let i=0; i < temperatures.length; i++){
        let ans = 0;
        while(i+ans < temperatures.length){
            ans++;
            if(temperatures.at(i+ans) > temperatures.at(i)){
                stack.push(ans);
                break;
            }
            if(i+ans == temperatures.length){
                stack.push(0);
            }
        }
    }
    return stack;
};

 

이렇게 풀면 아니나다를까 TimeLimit Exceeded 뜸ㅎㅎ

 

 

아니 근데 이건 너무한 거 아니냐고ㅋㅋㅋ [99, 99, 99, 99, .... , 100] 이 테스트케이스였다;;;

코드 구조가 비효율적인것과는 별개로, Array.at()은 맨 끝에서부터 접근이 필요한 게 아니라면 굳이 안 쓰는 게 더 낫다.

 

 

Monotonic Stack을 이용해서 풀라고 준 문제니까 그 방식으로 풀어 보자.

 

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    // 더 따뜻한 날이 될때까지 걸리는 일수를 리턴, 같은 날만 있거나 없으면 0
    const stack = [];
    const result = new Array(temperatures.length).fill(0);
    for(let i=0; i < temperatures.length; i++){
         while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex; // 며칠 뒤인지 계산
        }
        stack.push(i);
    }
    return [];
};

 

훨씬 깔끔하네요.

 

var dailyTemperatures = function(temps) {
	const length = temps.length;
	let result = new Uint32Array(length);
	for (let i = length - 2; i >= 0; i--) {
		const ct = temps[i];
		let j = i + 1
		while (temps[j] <= ct && j < length) {
			if (result[j] === 0) {
				j = length;
				break;
			}
			j = j + result[j]
		}
		if (j < length) {
			result[i] = j - i;
		}
	}
	return result;
}

 

이렇게 DP로 푼 사람도 있었다ㅋㅋㅋㅋ

세상은 넓고 잘하고 열심히 하는 사람도 참 많다...