LeetCode - Daily Temperatures

문제

지문

주어진 정수 배열 temperatures는 일일 온도를 나타내며, 배열 answer는 다음과 같이 반환됩니다. answer[i]는 i번째 날 이후 따뜻한 온도를 얻기 위해 기다려야 하는 날의 수입니다. 이러한 경우가 없는 경우에는 answer[i] == 0으로 유지됩니다.

예시

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]

제약 조건

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

문제 링크
https://leetcode.com/problems/daily-temperatures/description/

풀이

문제 이해하기 단계

• input, output을 확인한다.
  • input과 output은 정수 배열이다.
  • input의 범위는 30이상 100이하다.
• input size N을 확인한다.
  • 시간복잡도를 계산하기 위한 N은 input 배열의 길이다.
• 제약 조건을 확인한다.
  • temperatures.length의 최댓값이 10^5이다.따라서 n^2 이상의 시간복잡도를 사용하면 안된다.

접근 방법 생각하기

• 직관적으로 생각해보기
  • 모든 날의 온도가 같다면 출력은 전부 0일 것이다.
  • 매일 온도가 상승하면 출력은 마지막 요소를 제외하고 1일것이다.
  • 매일 온도가 하락하면 출력은 전부 0일 것이다.
• 자료구조와 알고리즘 활용
  • 이 문제는 순차적으로 각 날짜의 온도를 비교하면서 특정 조건이 충족될 때 날짜의 차이를 계산해서 결과에 반영한다.
  • 순차적인 비교 , 그리고 조건 충족 시 처리 가 필요할 때는 Stack 자료구조를 사용하는 것이 좋다.

코드 설계

1. 반복문으로 온도 배열 전체를 순회한다.
2. 현재 날짜를 스택에 저장한다.
3. 만약 스택이 비어있지 않고 현재 온도가 스택의 최상단에 저장된 온도보다 높다면 스택을 제거한다.
4. 스택에 저장된 날짜를 인덱스로 설정하고 output 배열에 현재 날짜와 저장된 날짜의 차이를 저장한다.

코드 구현

public static int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();

        for (int currentDay = 0; currentDay < temperatures.length; currentDay++) {
            while (!stack.isEmpty() && temperatures[currentDay] > temperatures[stack.peek()]) {
                int prevDay = stack.pop();
                result[prevDay] = currentDay - prevDay;
            }
            stack.push(currentDay);
        }

        return result;
    }

• 정수형 배열의 요소는 자동으로 0으로 초기화된다. 따라서 현재 온도보다 높은 경우가 없는 날의 값은 자동으로 0이 설정된다.