[리트코드] 739. Daily Temperatures

in 코딩테스트 on 리트코드




739. Daily Temperatures

리트코드

나의 풀이 (61000ms)

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  const answer = [];
  for (let i = 0; i < temperatures.length; i++) {
    let cnt = 1;
    let flag = false;
    for (let j = i + 1; j < temperatures.length; j++) {
      if (temperatures[i] < temperatures[j]) {
        answer.push(cnt);
        flag = true;
        break;
      }
      cnt++;
    }
    if (!flag) answer.push(0);
  }
  return answer;
};


뒤에 배열들을 순환하면서 도는게 가장 확실하지만, 최악의 경우 O^2 이 나오기 때문에 효율성이 좋지 못하다.
결과도

Runtime: 1336 ms, faster than 27.20% of JavaScript online submissions for Daily Temperatures.

로 별로 좋지 않게 나왔다.
더 효율적인 코드를 알아보자



best 풀이 (54000ms)

var dailyTemperatures = function(temperatures) {
  for (let i = 0; i < temperatures.length; i++) {
    let j = i + 1;
    while (temperatures[i] >= temperatures[j]) {
      j++;
    }
    temperatures[i] = temperatures[i] <= temperatures[j] ? j - i: 0;
  }
  return temperatures;
};



best 풀이 (58000ms)

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    var result = new Array(temperatures.length);
    result.fill(0);
    for(var i = 0; i < temperatures.length; i++) {
        var curTemp = temperatures[i];
        for(var j = i + 1; j < temperatures.length; j++) {
            if(temperatures[j] > curTemp) {
                result[i] = j - i;
                break;
            }
        }
    }
    return result;
};