[LeetCode/MEDIUM] 739. Daily Temperatures (JAVA) : 문제&풀이

 

 

각 기온이 보다 높게 갱신되는데 걸리는 일자를 구하는 문제이다.

e.g. {50, 51, 48, 47, 53} → {1, 3, 2, 1, 0}

     ∵ 50 → 51 : 1일 소요 / 51 → 53 : 3일 소요 / … /  53 : 마지막

int배열을 매개변수로 받는 dailyTemperatures 메서드의 틀이 주어진다.

 

Problem :

public class DailyTemperature {
    public int[] dailyTemperatures(int[] temperatures) {

    }
}

 

풀이는 dailyTemperatures에 작성하면 된다.

 

Solution :

1. 결과 배열을 생성 및 초기화한다.
2. 첫 기온을 Stack에 담는다.
3. temperatures 배열을 순서대로 돌며
   1. 지난 기온보다 현재 기온이 높으면 며칠 차이인지 기록한다.
   2. 이번 index를 Stack에 담는다.
4. 결과 배열을 리턴한다.

import java.util.Arrays;
import java.util.Stack;

public class DailyTemperature {

    // time complexity : for loop -> O(n)
    // space complexity : stack to push number of 'int[] temperatures' -> O(n)
    public int[] dailyTemperatures(int[] temperatures) {
        // return DataStructure (initialized with 0s)
        int[] result = new int[temperatures.length];

        // stack of non-match temperatures (for reverse-comparisons)
        Stack<Integer> tempStack = new Stack<>();

        for (int i = 0; i < temperatures.length; i++){
            while(!tempStack.empty() && temperatures[tempStack.peek()] < temperatures[i]){
                int idx = tempStack.pop();
                result[idx] = i - idx;
            }
            tempStack.push(i);
        }

        return result;
    }
}

 

이해하기 쉽게 그림으로 표현하면 다음과 같다.

 

Complexity :

• 시간복잡도 (Time Complexity)
  • for문 사용에 따라 O(n)
• 공간복잡도 (Space Complexity)
  • 매개변수 temperatures를 담아둘 Stack 사용에 따라 O(n)

 

Sample(Test) :

import java.util.Arrays;
import java.util.Stack;

public class DailyTemperature {

    // time complexity : for loop -> O(n)
    // space complexity : stack to push number of 'int[] temperatures' -> O(n)
    public int[] dailyTemperatures(int[] temperatures) {
        // return DataStructure (initialized with 0s)
        int[] result = new int[temperatures.length];

        // stack of non-match temperatures (for reverse-comparisons)
        Stack<Integer> tempStack = new Stack<>();

        for (int i = 0; i < temperatures.length; i++){
            while(!tempStack.empty() && temperatures[tempStack.peek()] < temperatures[i]){
                int idx = tempStack.pop();
                result[idx] = i - idx;
            }
            tempStack.push(i);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] temperatures = new int[]{73, 74, 75, 71, 69, 72, 76, 73};
        // {1, 1, 4, 1, 1, 0, 0}

        DailyTemperature d = new DailyTemperature();
        System.out.println(Arrays.toString(d.dailyTemperatures(temperatures)));
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

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