[LeetCode] 739. Daily Temperatures

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

Daily Temperatures - LeetCode

Algorithm

처음 완전탐색을 생각했으나 O(n^2)의 시간복잡도여서, 고민에 빠졌던 문제이다. 혹여나 나와같이 이해가 되지않는 사람을 위해 풀이를 상세히 남겨보려고한다.

 

우선 이 풀이를 보기전, Monotic stack이란 개념에 대해 이해하여야한다. 개인적으로 다음 글 을 참조했는데, 대략적으로 정리해본 바로는 아래와 같다.

• 단조 스택은 원소가 Increasing / Decreasing으로 정렬되어 있는 배열을 뜻한다.
• 해당 스택 자체로 유용함은 없지만, 정렬 과정에서 발생하는 정보들이 유용하다.
• 이를 사용하면 O(n^2) 의문제도 O(n)으로 쉽게 풀 수 있을 수 있다.

위의 첫번째 예시를 보면 [8,6,4,2]에 4를 추가할때, monotonic stack은 decreasing순서를 지키기 위해 3,2 를 pop()하고 4를 넣는다. 이렇게 하면  4의 가장 가까운 큰 숫자는 옆의 숫자인 6임이 명백해진다.

 

이어 두번째 예시를 보자. [4,6,8,1,2]에서 가장 가까운 큰 수 인덱스를 찾는다고 해보자. monotonic stack에서 특정원소의 가장 가까운 큰 숫자는 바로 앞의 숫자임이 명백하므로, 이를 이용해 문제를 풀어나갈 수 있다.

 

이제 이를 활용해 풀어보도록 하자.아래 시뮬레이션을 따라가보자.

먼저 위에서 stack은 monotonic stack이다. 각 temperature 를 탐색하며, monotonic stack을 만든다.

 

73: stack이 비었으므로 73을 넣는다.

74: 73 < 74이므로 73을 pop()한다. 그리고 output 해당 인덱스 자리에 74와의 인덱스 차(1) 를 넣는다. 그 후 stack에 74를 넣는다.

75: 74 < 75이므로 74를 pop()한다. 그리고 output 해당 인덱스 자리에 75와의 인덱스 차(1) 를 넣는다. 그 후 stack에 75를 넣는다.

71: 75 > 71 이므로 stack에 원소 삽입

69: 71 > 69 이므로 stack에 원소 삽입

72: 69 < 72 이므로 69를 pop()한다. 그리고 output 해당 인덱스 자리에 74와의 인덱스 차(1) 를 넣는다.  나머지 원소(71)에 대해서도 이를 반복한다. 그리 후 stack에 72를 넣는다.

76: 75 < 76이므로 75를 pop()한다. 그리고 output 해당 인덱스 자리에 76와의 인덱스 차(1) 를 넣는다. 그 후 stack에 76를 넣는다.

73: 76 > 73 이므로 stack에 원소 삽입

여기서 monotic stack은 [76,73]이고, 이 인덱스들은 더이상 높은 기온이 나오지않았음을 뜻하므로 남은 값을 0으로 채워 준다.

 

결국 이 문제의 핵심은 모노토닉 스택(monotonic stack)을 사용하여 다음으로 높은 기온이 나올 때까지의 일 수를 계산하는 것이다.

즉, 더 풀어 설명하자면, 예를들어 [72,67,66,54..] 처럼 단조감소 스택이 있을때,여기에 온도 99가 추가된다면 본 스택원소들의 가장 가까운 큰 수는 99임이 명백하다!

이를 활용하면 O(n^2)이 아니라 배열을 순회하며 값을 구하는 효율적 풀이를 구현할 수 있다.

---

Python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = [] # pair: [temperature, index]

        for i, t in enumerate(temperatures): # temperature 순회
            while stack and stack[-1][0] < t:
                stackT, stackInd = stack.pop()
                res[stackInd] = i - stackInd # 인덱스 거리 차
            stack.append((t, i)) # 새 원소 삽입
        return res

Java

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for(int currDay = 0; currDay < temperatures.length; currDay++){
            while(
                !stack.isEmpty() &&
                temperatures[stack.peek()] < temperatures[currDay]
            ) {
                int prevDay = stack.pop();
                res[prevDay] = currDay - prevDay;
            }
            stack.add(currDay); // stack에 인덱스 저장
        }
        return res;
    }
}