[LeetCode] 739 - Daily Temperatures [Swift]

문제 링크

Daily Temperatures - LeetCode

문제

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

 

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].

 

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

 

문제 풀이

이 문제는 배열의 값을 기준으로 문제를 푸는 것이 아닌 배열의 인덱스를 기준으로 문제를 풀어야 했어요.

주어진 배열의 값보다 큰 값이 얼마나 멀리 떨어져 있는지를 찾는 것이 이 문제의 목표인데요, 일단 O(n^2) 방법으로 하나씩 모두 보는 방법이 있습니다.

주어진 예로 O(n^2) 방법을 살펴보면!

위의 그림과 같이 어떤 지점의 수보다 뒤에 존재하는 수들을 더 큰 값이 나올 때까지 하나씩 모두 체크하면 됩니다.

제일 직관적인 방법입니다.

이걸 구현하면 아래와 같이 구현할 수 있어요.

class Solution {
    func dailyTemperatures(_ T: [Int]) -> [Int] {
        var result = [Int](repeating: 0, count: T.count)
        for i in 0..<T.count {
            for j in i+1..<T.count {
                if T[i] < T[j] {
                    result[i] = j - i
                    break
                }
            }
        }
        return result
    }
}

하지만 이렇게 구현하게 되면 시간 초과가 발생하여 문제를 해결할 수 없어요.

 

따라서 더 효율적인 방법을 찾아야 합니다.

효율적인 방법을 위해서는 스택을 사용하면 됩니다.

위와 같이 스택에는 인덱스 값을 넣어줍니다.

위의 그림은 첫 번째 인덱스 값인 0을 스택에 넣는 과정이에요.

그럼 위와 같이 두 번째 값과 스택에 존재하는 값을 비교해봅니다.

만약 현재 값이 더 크다면 결괏값을 (현재 인덱스 - 스택의 꼭대기 값)로 만들어주면 됩니다.

 

그럼 좀 더 스택에 인덱스가 많은 상황을 살펴볼까요?

위의 그림은 배열의 여섯 번째 값인 72를 볼 때 스택의 상태입니다.

스택에는 3개의 값이 들어가 있는데요, 스택의 특성이 LIFO이므로 마지막에 들어간 값부터 차례대로 꺼내면서 확인하면 됩니다.

72보다 큰 값을 만날 때까지 계속 꺼내면 됩니다.

 

위의 과정을 순서대로 나열하면 아래와 같아요.

1. 주어진 배열의 크기만큼 0으로 채워진 정답 배열을 준비합니다.
2. 빈 스택을 준비합니다.
3. 주어진 배열을 0번 인덱스부터 4~5를 반복합니다.
4. 배열이 비었거나 배열의 마지막 값이 현재 값보다 크다면 현재 인덱스를 스택에 넣습니다.
5. 만약 배열의 마지막 값이 현재 값보다 작다면 스택에서 값을 꺼내 현재 값과 꺼낸 값의 차이를 정답 배열에 저장합니다.

위의 과정을 코드로 구현하면 문제를 풀 수 있습니다!

소스 코드

class Solution {
    func dailyTemperatures(_ T: [Int]) -> [Int] {
        var stack: [Int] = []
        var result = [Int](repeating: 0, count: T.count)
        for i in 0..<T.count {
            // 스택이 비어있거나 현재 온도가 스택의 마지막 값보다 클 경우
            // -> 이 경우가 이 문제에서 찾고자 하는 부분!
            while !stack.isEmpty && T[i] > T[stack.last!] {
                let index = stack.removeLast()
                result[index] = i - index
            }
            stack.append(i)
        }
        return result
    }
}