[LeetCode Medium] Daily Temperatures JavaScript

IT공부중·2020년 5월 6일
0

알고리즘

목록 보기
28/49

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

문제 설명

T라는 숫자 배열이 주어진다. T = [73, 74, 75, 71, 69, 72, 76, 73]
그러면 이제 각각 자신 보다 더 큰 온도가 나올 때까지 얼마나 걸렸는지를 반환해주면 된다. 이 식에서 답은 [1, 1, 4, 2, 1, 1, 0, 0]다 된다.
0번 index는 73이니깐 73보다 높은 값이 나올 때까지 몇번 걸렸는지.. 다음 index가 74이기 때문에 1, 74도 75까지 한번이기 때문에 1, 75는 75보다 큰 값이 나오기 까지 4번 걸린다... 이렇게 해서 리턴해주면된다.

문제 풀이

가장 쉽게 푸는 방법은 2중 for문을 사용해서 하나하나 다 탐색해보는 방법이다. 내가 다른 방법이 생각이 안 나서 일단 2중 for문으로 풀었다. 이렇게 풀면 마지막은 검사가 되지 않아서 for문이 끝나고 난 후 0을 한번 push 해주었다.

나의 코드

var dailyTemperatures = function(T) {
    let length = T.length;
    let answer = [];

    for (let i = 0; i < length; i++){
        for (let j = i+1; j < length; j++){
            if(T[i] < T[j]) {
                answer.push(j-i);
                break;
            }
            if(j == length-1) {
                answer.push(0);
            }
        }
    }
    answer.push(0);
    return answer;
};

더 좋은 풀이

더 좋게 푸는 방법이 생각이 잘 안 나서 다른 사람이 푼 것을 찾아보았다. 푸는 방법은 Stack을 사용하여 푸는 방법이었다. Stack을 만들어 놓고 Stack이 없을 땐 index를 넣어두고 Stack이 있을 땐 Stack의 맨 위와 현재 값을 비교한다. 그래서 현재값이 더 크면 Stack에서 빼내고 해당 index의 정답을 인덱스의 차이로 바꿔준다. while 문으로 계속 해주면 된다.
Stack 더 안에 있는 index 들은 Stack 맨 위에 있는 index 보다 더 큰 값들이기 때문에 Stack 맨 위가 조건에 통과 되지 않으면 나머지들은 그냥 넘어가도 되는 것이다.
2중 for문을 사용했을 때 보다 훨씬 적게 비교를 할 수 있다.

더 좋은 코드

var dailyTemperatures = function(T) {
    let stack = [];
    let answer = new Array(T.length).fill(0);
    for(let i = 0; i < T.length; i++) {
        while(stack.length && T[i] > T[stack[stack.length-1]]) {
            let temp = stack.pop();
            answer[temp] = i - temp;
        }
        stack.push(i);
    }
    return answer;
 };
profile
4년차 프론트엔드 개발자 문건우입니다.

0개의 댓글