Stack | 739. Daily Tempuratures

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

 

일일 기온 정보가 저장된 배열 temperatures가 주어지고, 각각의 날짜별 기온보다 더 높은 기온이 나타나는데 며칠이 걸리는지 구하는 문제이다. 만약 더 높은 기온이 없다면 0을 저장한다.

 

각 날짜에서 며칠을 기다려야 하는지 배열에 저장했다면 더 이상 이전의 날짜 정보를 저장할 필요가 없으므로 스택 자료구조를 사용하면 빠르게 접근할 수 있을 것으로 생각했다.

1. 스택에는 기온 대신 본인보다 더 높은 기온을 만나지 못한 기온의 인덱스를 저장.
2. 스택의 top에는 가장 높은 기온의 인덱스가 저장 될 수 있도록 함.
3. 스택 안에 있는 기온은 더 높은 기온을 만나지 못한 날짜이므로 top보다 더 높은 기온을 만났다면 스택이 빌 때까지 pop을 반복.
4. 이 때, 스택을 비우면서 현재까지의 가장 높은 기온과의 거리를 인덱스의 차로 구하여 ans배열에 저장.

 

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> st = new ArrayDeque<>();
        int[] ans = new int[temperatures.length];
        for(int i = 0; i < temperatures.length; i++){
            while(!st.isEmpty() && temperatures[i] > temperatures[st.peek()]){
                int idx = st.pop();
                ans[idx] = i - idx;
            }
            st.push(i);
        }
        return ans;
    }
}

 

이 코드의 시간복잡도를 구할 때 for 와 while문을 중첩하여 구현하였기 때문에 O(n^2)이라고 생각할 수도 있지만, while문은 코드가 끝날 때 까지 n번만 반복되므로 최대 O(2n) ≒ O(n)의 시간 복잡도를 가지게 된다.

 

 

다른 문제를 풀 때도 주어진 데이터의 값을 활용할 지, 인덱스를 활용할 지를 생각해보면서 풀면 좋을 것 같다.