[자바 알고리즘 인터뷰] 9장 스택, 큐 (3) 일일 온도

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

 

 

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

 

 

풀이 1) 스택 값 비교 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자: 박상길 <책만>

 

 

- 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교해서, 더 높다면 다음과 같이 스택의 값을 pop()으로 꺼내고, 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 업데이트 

 

- 그리고 현재 인덱스를 다시 스택에 삽입한다. 

 

 //현재 온도가 스택에 있는 온도보다 높다면 꺼내서 결과를 업데이트
 while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()])
 {
     int last = stack.pop();
     result[last] = i-last;
 }
  //현재 인덱스를 스택에 삽입
  stack.push(i);

 

 

ex)

- 인덱스가 5인 지점에서 스택에는 [2,3,4]가 있다. 

- 인덱스 2부터는 계속 온도가 떨어지기만 하면서 처리되지 못하고 스택에 계속 쌓였다. 

- 인덱스 5의 온도는 22, 스택에 있는 2,3,4의 온도는 각각 25,21,19 이다. 

- 22는 25,21,19보다 높기 때문에 현재 인덱스와 21과의 인덱스와는 두칸 차이로 정답은 2가 되고, 19의 인덱스와는 한 칸 차이로 정답은 1이다. 

- 처리한 인덱스는 스택에서 팝으로 제거된다 

- 25도인 인덱스 2는 현재 온도 보다 높기 때문에 계속 스택에 남아 있게 된다. 

 

- 다음 차례인 인덱스 6에서 스택에는 [2,5]가 남아 있고, 각각 25,22이다. 

- 이제 현재 온도 26도는 22나 25보다 높기 때문에 스택은 모두 처리되어 비워질 것이다. 

- 22의 인덱스와는 한 칸 차이로 정답은 1이고 25의 인덱스와는 무려 4칸 차이가 난다. 

- 이보다 높은 온도가 그간 나오지 않았기 떄문에 스택에서 비워지지 못하고 계속 남아 있다가 이제서야 처리가 된다. 

 

- 디폴트는 0이다. 

- 만약 더 높은 온도가 나오지 않아 스택이 비워지지 않았다면 해당 인덱스는 정답이 되지 못하고 디폴트인 0으로 남게 된다. 

 

import java.util.*;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        //결과를 담을 정수형 배열
        int result[] = new int[temperatures.length];

        //결과 처리를 위한 스택 선언
        Deque<Integer> stack = new ArrayDeque<>();

        for(int i=0; i<temperatures.length; i++)
        {
            //현재 온도가 스택에 있는 온도보다 높다면 꺼내서 결과를 업데이트
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()])
            {
                int last = stack.pop();
                result[last] = i-last;
            }
             //현재 인덱스를 스택에 삽입
             stack.push(i);
        }

    return result;
    }
}

23밀리초