Daily Temperatures (Stack)

LeetCode의 Queue, Stack 튜토리얼의 세 번째 문제인 Daily Temperatures다. 프로그래머스의 주식 가격과 비슷한 문제인데 예전에 풀 때는 못 풀었지만 이번에 LeetCode에서 다른 도움 없이 혼자 풀 수 있었기 때문에 프로그래머스의 문제도 풀 수 있을 것이다.

Explore - LeetCode

이번 문제의 조건은 다음과 같다.

• 며칠간의 기온을 담고 있는 정수형 배열 T가 주어진다.

• 각 날짜의 기온마다 현재 기온보다 높은 기온이 나올 때까지 며칠이 걸리는지 측정한다.

• 측정값을 담고 있는 배열을 반환한다.

얼핏 들으면 잘 이해가 안 될 수도 있지만 예시를 보면 다음과 같다.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

예시에서는 8일간의 기온으로 [73, 74, 75, 71, 69, 72 ,76, 73]이 주어졌는데 순서대로 1일부터 8일까지라고 해보자. 1일째에는 73도의 기온이며 2일째에는 74도의 기온이다. 이때 1일째의 기온이 1일 이후(2일째) 상승했으므로 결과 배열에는 1이 삽입되어야 한다. 2일째의 기온도 하루만 기다리면 온도가 상승하기 때문에 1이 삽입되어야 하는데 3일째의 기온부터는 온도가 올라가지 않는다.

 

3일째부터는 75도에서 4일째의 71도로 기온이 하락했기 때문에 아직 기다려야 한다. 그리고 5일째의 69도도 기온이 하락했기 때문에 기다려야 하며 6일째의 72도에서 기온이 조금 올라갔기 때문에 결과 배열의 4일째, 5일째 위치에는 2, 1이 삽입되어야 한다. 왜냐면 4일(71도)에서 이틀을 기다려서 72도(6일)가 되었으며 5일(69도)에서 하루를 기다려서 72도(6일)가 되었기 때문이다. 그리고 7일째에서 76도로 상승했기 때문에 결과 배열의 3일째 위치에 4가 삽입되어야 한다. 즉 기온이 언제 다시 지금보다 높아지는지 측정하는 게 이번 문제의 목표가 된다.

 

기온들이 순서대로 하락세가 끝난다면 참 좋겠지만 위의 예제처럼 4, 5, 6일이 먼저 계산되고 3일째가 계산되는 등 현재의 기온이 언제 다시 원점을 회복하고 높아질지 알 수 없다. 그렇기 때문에 이를 스택에 저장해 두고 기억하는 방법을 생각해볼 수 있으며 고민하다가 생각한 방법은 스택을 두 개 사용하는 것이다.

 

내가 생각한 풀이의 핵심 로직은 현재 기온이 이전 기온보다 높은 기온일 경우 기온들이 저장된 스택에서 현재 기온보다 높은 기온이 나올 때까지 기온들을 삭제하는 것이다. 그리고 삭제하는 과정에서 인덱스의 차이 즉 날짜의 차이를 계산하여 해당 기온보다 높아지기 위해 며칠 동안 기다렸는지 파악하는 것이다. 이를 그림으로 보이면 다음과 같다. 

스택 하나는 기온의 온도를 저장하고 위의 그림에는 그리지 않았지만 다른 스택은 해당 기온의 인덱스를 저장한다. 이 두 스택은 같이 삽입되고 같이 삭제된다. 그냥 기온과 그 기온의 인덱스, 즉 날짜를 기억하기 위해 스택을 두 개 사용한 것이며 더 좋은 방법이 있다면 스택을 하나만 사용할 수도 있을 것이다. 여기선 내가 처음에 생각한 풀이를 기반으로 진행하겠다.

 

기온을 저장하는 스택이 비어있다면 첫 번째 기온이기 때문에 다른 기온과 비교하지 않고 그대로 삽입한다. 다음 기온부터는 스택에 들어있는 기온값과 현재 기온을 비교하여 현재 기온이 더 높은 기온일 경우 스택에 들어있는 기온값을 빼내고 현재 기온의 인덱스와 스택에서 삭제된 기온의 인덱스의 차이, 즉 온도가 상승하기까지 며칠이 지났는지를 계산하여 결과 배열에 저장한다. 이때 이 삭제된 기온을 기준으로 며칠이 지났는지 계산해야 하기 때문에 결과 배열에서 저장되는 위치는 삭제된 기온의 인덱스이며 이 인덱스를 기억하기 위해 두 번째 스택을 사용하는 것이다.

 

그냥 indexOf 같은 메서드를 사용해서 찾으면 되지 않나? 싶지만 중복되는 기온값이 있기 때문에 그리고 Stack 튜토리얼인 만큼 최대한 Stack을 활용해서 풀어보는 방향으로 가닥을 잡았다. 이때 기온이 현재 기온보다 높아야 즉 초과해야 하기 때문에 조건을 헷갈리지 않도록 주의해야 한다. 이를 바탕으로 작성한 코드는 다음과 같다.

import java.util.Stack;


class Solution {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> tIndexes = new Stack<>();
    private int[] result;
    
    public int[] dailyTemperatures(int[] T) {
        int limit = T.length;
        result = new int[limit];
        
        for(int index = 0; index < limit; index++){
            int currentT = T[index];
            
            if(stack.empty()) {
                stack.push(currentT);
                tIndexes.push(index);
                continue;
            } 
            
            if(currentT > stack.peek()){
                do {
                    int TIndex = tIndexes.pop();
                    result[TIndex] = index - TIndex;
                    stack.pop();
                }
                while(!stack.empty() && stack.peek() < currentT);
            } 
            
            stack.push(currentT);
            tIndexes.push(index);
        }
        
        return result;
    }
}

주어진 기온들의 배열을 반복문을 사용하여 처음부터 참조하고 있다. 기온을 저장하는 스택인 stack과 기온들의 인덱스를 저장하는 스택인 tIndexes를 생성하여 스택에 요소를 삽입하거나 삭제할 때마다 같이 동작하는 것을 볼 수 있다.

 

언급했듯이 스택이 비어있다면 비교할 기온도 없기 때문에 현재 확인하고 있는 기온(currentT)을 스택에 삽입한다. 그렇지 않다면 스택에서 기온을 하나 꺼내서(stack.peek()) 현재 기온과 비교한다. 만약 현재 기온이 스택에 있던 기온보다 높다면(stack.peek() < currentT) 스택에서 기온을 하나 삭제하고 현재 인덱스(index)와 해당 기온의 인덱스(TIndex)의 차이를 결과 배열에 저장한다. 이 차이는 기온이 높아지기까지 얼마나 걸렸는지에 해당한다. 그렇기 때문에 스택에서 기온이 하나씩 삭제될수록 그 간격은 점점 증가하게 되는데 'index - TIndex'의 TIndex는 기온의 인덱스를 저장하는 스택에서 하나씩 빼는 값이기 때문에 점점 줄어들게 된다. 즉 날짜 사이의 간격이 점점 늘어난다는 것이 된다. 마지막으로 현재 인덱스의 기온도 내일의 기온과 비교되어야 하기 때문에 다시 스택에 삽입하면서 반복문을 마친다.

 

만약 어떤 날 이후로 기온이 더 높아지는 날이 없다면 해당 날짜의 결과는 0을 가져야 한다. 그래서 결과 배열은 0으로 초기화되는 게 바람직하며 자바에서는 정수형 배열을 선언했을 때 0으로 초기화되기 때문에 따로 초기화하는 로직을 적용하진 않았다.

아쉽게도 성능은 하위 25%에 그친 것을 볼 수 있었다. 아마 스택을 두 개나 사용해서 그런 것 같은데 다른 우수한 풀이를 살펴보니 다음과 같은 로직을 사용하는 것을 볼 수 있었다.

class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> s = new Stack<>();
        int[] res = new int[T.length];
        for(int i = 0; i < T.length; i ++) {
            while(!s.empty() && T[i] > T[s.peek()]) {
                int idx = s.pop();
                res[idx] = i - idx;
            }
            s.push(i);
        }
        return res;
    }
}

풀이를 보니 스택을 하나만 사용해도 풀 수 있는 문제였다. 로직 자체는 생각했던 것과 비슷하지만 인덱스 변수를 활용해서 불필요한 스택을 사용하지 않는 점이 인상 깊었다. 나는 do-while로 스택이 비어있지 않는 경우에만 peek()해서 기온을 비교했는데 여기서는 while 조건에 스택의 empty() 메서드를 활용한 것을 볼 수 있었다. 그리고 기온이 저장된 배열은 파라미터로 주어지기 때문에 어디서든 쉽게 참조할 수 있어 굳이 스택을 유지하지 않고 인덱스만 스택으로 유지해도 된다는 것을 확인할 수 있었다.

 

그 외에는 스택에서 하나씩 비교하고 현재 기온보다 낮은 기온일 경우 결과 배열에 날짜 사이의 간격(i - idx)을 저장하면서 동일하게 진행하는 것을 볼 수 있다.

 

 

프로그래머스에서 처음 봤을 때는 분명 스택을 이용해서 푸는 문제 같긴 한데 어떻게 풀어야 될지 도저히 감이 잡히지 않았다. 이번 리트코드에서 봤을 때도 영 모르겠어서 풀이를 볼까 하다가 그냥 머리를 식힐 겸 밖에 나가려고 엘리베이터에 탔을 때 곰곰이 생각해보니 위의 풀이가 떠올라서 집에 와서 몇 번 시도해본 결과 구현할 수 있었다. 이걸 바탕으로 프로그래머스의 그 문제도 풀 수 있었으면 좋겠다.