8주차. 스택, 큐(일일 온도)

22. 일일 온도

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

Daily Temperatures - LeetCode

📌문제
매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라.

- 예제1
  📝입력

temperatures = [73,74,75,71,69,72,76,73]

  💻출력

[1,1,4,2,1,1,0,0]

 - 예제2

  📝입력

temperatures = [30,40,50,60]

  💻출력

[1,1,1,0]

    
📌풀이(스택 활용)

149ms, 58mb

public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < temperatures.length; i++){
            // 스택에 들어간 이전 인덱스의 값보다 현재 값이 크면 온도가 올라간 것이지 체크해야함
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                int last = stack.pop();
                answer[last] = i - last; // 이전 인덱스의 값과 현재 값을 빼서 그 차이를 배열에 넣음
            }
            stack.push(i);
        }
        return answer;
    }

이전 문제와 똑같이 Runtime 시간이 어마어마해서 다른 문제 풀이 법을 찾아봤다.

 

📌풀이(배열)

7ms, 56.6 MB

public static int[] dailyTemperatures2(int[] T) {
    int[] result = new int[T.length];
    // 끝에서 부터 시작
    for (int day = T.length - 1; day >= 0; day--)
        for (int i = day - 1; i >= 0 && T[i] < T[day]; i--)
            result[i] = day - i;
    return result;
}

끝에서 부터 이전 온도의 값과 비교하여 뺀값을 넣어주는 방법으로 시간복잡도가 매우매우 줄어들었으며, 코드량도 상당히 짧아졌다.

 

사람들은 어떻게 이런 생각을 하는 걸까...