본문 바로가기
Coding Test/Stack

[Leetcode] 739번 - 일일 온도

Dev D. john park 2025. 8. 12. 15:09

1. 문제 파악

  1. 문제 링크: https://leetcode.com/problems/daily-temperatures/description/
  2. 문제 정의: 배열을 순회하면서 현재 지정된 배열 요소보다 큰값이 몇 번째 뒤에 위치하는지 저장하는 배열 반환
  3. 문제의 제약 파악 (입력값 크기, 상수 조건)
    • 1 <= temperatures.length <= 105: 시간복잡도가 O(N) 이내여야 통과하는데 안전하다.
    • 30 <= temperatures[i] <= 100

2. 문제 풀이

1. 브루트 포스로 문제 풀이 도출

  1. 주어진 배열과 동일한 크기의 반환 배열을 초기화한다.
  2. 배열을 순회하면서 순차적으로 요소 하나를 지정
  3. 지정된 요소의 이후 배열 요소를 순회하면서, 지정된 요소보다 큰 요소 중에 가장 가까운 요소를 찾는다.
  4. 지정된 요소의와 지정된 요소보다 큰 요소 중에 가장 가까운 요소의 인덱스 차이를 구한다.
  5. 인덱스 차이를 반활 배열에 저장한다.
for (int i = 0; i < temperatures.length; i++)
    for (int j = i + 1; j < temperatures.length; j++)
// ...

 

두개의 요소를 찾기 위해서 이중 순회를 해야하므로 시간복잡도는 O(N^2)이다.

 

2. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?

  1. O(N)에 배열 순회를 하면서 결과값 연산을 끝내야한다.
  2. 예를 들어, 75를 순회할때 76에 대한 연산이 끝나야한다. -> 배열을 첫번째 요소부터 순차적으로 순회하므로 말이 안된다.
  3. 그렇다면, 76를 순회할때 75에 대한 연산이 끝낼수있나? -> 배열을 첫번째 요소부터 순차적으로 순회할때 이전 요소를 저장할수 있다.
  4. 이렇게 이전 온도들을 저장해두면, 미래에서 온도가 올라가는 순간 한꺼번에 처리 가능하다. Ex) 71와 69를 저장했을때 72를 만나면 한번에 처리 가능
73 74 75 71 69 72 76 73

 

그러면 이전 요소를 저장할 자료구조는 다음 조건을 만족해야한다.

  • 앞에서 본 값을 저장한 다음에 O(1)내로 값을 가져와야한다. 그래야 배열 순회인 O(N) 내에 반환 배열에 저장할 값의 연산이 끝나야하기 때문이다.
  • 저장 순서를 기억하고 있어서 가장 최근에 저장한 값을 가져올수있어야한다. 그래야 현재보다 높은 온도중에 가장 가까운 온도를 찾을수 있기 때문이다. Ex) 72를 순회할때, 75, 71, 69 순으로 저장되어 있어야지 여기서 72 보다 작은 71와 69를 처리하고 삭제할수있다.

이를 만족하는 자료구조는 스택이 있다. 배열을 순회하면서 스택에 요소를 저장하고 최근에 저장한 값과 순회중 현재 지정한 값을 비교할수있다. 그러면 순회중 지정한 값과 스택에 저장되어 있는 값을 하나씩 꺼내서 작으면 갭차이를 결과값 배열에 저장하면된다.

 

예를들어, 배열 순회중 현재 지정된 요소가 5번 인덱스의 72라면, 이전에 스택에 저장했던 [75, 71, 69] 중에서 하나씩 요소를 꺼내서 72보다 작으면 갭차이를 저장하고 스택에 저장된 요소를 삭제하는 로직을 생각해볼수있다.

 

그리고 배열 요소값 말고 인덱스를 저장하면 주어진 배열의 요소값에 접근가능하므로, 현재 요소와 이전 요소의 인덱스의 차를 결과값으로 저장할수있다.

 

3. 입출력 케이스 도출 및 문제 풀이 도출 확인

  • 일반 케이스
    • 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]

4. 코드 구현

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

 

5. 복잡도

  • 시간 복잡도
    • 배열 순회: O(N)
  • 공간 복잡도
    • 추가 공간은 스택에 배열의 요소들을 저장하기 때문에 O(N)이다.

티스토리툴바