[Leetcode] 739. Daily Temperatures

 

[문제]

Daily Temperatures - LeetCode

 

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

 

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

 

Constraints:

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

 

문제 파악

-스택을 이용한 문제 풀이

접근 방법

-인덱스 거리를 비교해야하므로 배열 값이 아닌 인덱스 삽입

-스택의 최상단과 현재 요소 비교하여 현재 온도가 더 높으면 스택에서 빼기

-그 전까진 스택에 쌓아놓음. 그리고 현재 온도가 높으니 pop하고 그 이전 것도 비교하여 더 높으면 다 pop하기

[첫트]

-그래도 빠지지 않은 애들 = 온도가 높은 애들

-더 더워지는 날이 없었기 때문에 스택에 그대로 남아있는 것. = 0 return

-스택 저장 내용 = temps의 인덱스(몇째 날인지)

-pop하면서 현재 day(비교 대상)와 이전 날 인덱스 며칠 차이인지 계산하고 배열에 넣기

코드 구현

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

재구현

import java.util.*;
class Solution {
    public int[] dailyTemperatures(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] result = new int[arr.length];
        int st = 0;
        for(int i=0;i<arr.length;i++){
            int pre=0;
            while(!stack.isEmpty() && arr[i]>arr[stack.peek()]){
                pre = stack.pop();
                result[pre] = i-pre;
            }
            stack.push(i);
            
        }
        return result;
    }
}

배우게 된 점

-배열의 몇번 째에 넣어야 하는지 확인 → 무슨 값을 넣는 것인지 먼저 파악

⇒ 스택에 넣는다고 치면, 뽑는 그 자리에 넣음

⇒ 높은 요소 x 나오면, pop()해서 저장되었던 인덱스 값과의 차를 계산해준다.   i-stack.pop()

(스택 - pop()하는 기준이 되는 값과 pop()하는 값(계속 바뀜)의 관계성 만들어주기)

 

-시간 복잡도 : O(n)

-시간 복잡도 계산할 땐 기계적으로 하지 않고 코드를 잘 이해해야 한다.