[Leetcode/Medium] 일일 온도 (739. Daily Temperatures, Swift)

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

 

🤔 문제 설명

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

만약, 현재로부터 더 따뜻한 날이 이후에 없을 경우에는 Array에 0을 담아 출력한다.

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

 

💡 풀이

(Index, temperature)로 이루어진 튜플(Tuple)과 스택(Stack)을 함께 활용해서 문제를 풀었다.

기본 스택의 원칙은 스택의 top값과 반복 중인 현재 온도를 비교해서 더 따뜻한 날씨가 들어온 경우에는 pop을 한다는 것이다.
그리고 인덱스의 차이값을 활용해서 따뜻한 날을 담은 배열을 업데이트 해나간다는 것이다.

위의 예시 문제 temperatures = [73,74,75,71,69,72,76,73]가 주어지는 경우를 살펴보자.
최종 반환할 resultTemperatures Array를 위 temperatures의 길이만큼 0으로 우선 초기화해줬다. 그리고 temperatures Array를 반복해주겠다.

• 반복 1. Index = 0, temperature = 73 : 스택이 비어있기 때문에 (0, 73)을 append 한다.
• 반복 2. Index = 1, temperature = 74, stack.last = (0, 73) : 새로운 온도가 더 따뜻하기 때문에 last를 pop하고, 결과 배열에 계산해서 업데이트 (0번째 인덱스에 1-0 = 1 업데이트 = 1일 만에 더 따뜻한 날을 만났다는 뜻) -> 이후 스택이 비어있기 때문에 (1, 74)를 append한다.
• 반복 3. Index = 2, temperature = 75, stack.last = (1, 74) : 새로운 온도가 더 따뜻하기 때문에 last를 pop하고, 결과 배열에 계산해서 업데이트 (1번째 인덱스에 2-1 = 1 업데이트 = 1일 만에 더 따뜻한 날을 만났다는 뜻) -> 이후 스택이 비어있기 때문에 (2, 75)를 append 한다.
• 반복 4. Index = 3, temperature = 71, stack.last =(2, 75) : 기존 온도가 더 따뜻하기 때문에 스택에 (3, 71) append
• 반복 5. Index = 4, temperature = 69, stack.last =(3, 71) : 기존 온도가 더 따뜻하기 때문에 스택에 (4, 69) append

여기까지 한번 끊어서 보면, 현재 스택에는 [(2, 75), (3, 71), (4, 69)]가 저장되어 있는 상황이다.

이후 6번째 반복으로 Index = 5, temperature = 72, stack.last =(4, 69)가 들어오는 상황을 보겠다.

• 반복 6-1. 새로운 온도가 더 따뜻하기 때문에 last를 pop 하고, 결과 배열에 계산해서 업데이트 (4번째 인덱스에 5-4 = 1 업데이트 = 1일만에 더 따뜻한 날을 만났다는 뜻) -> stack.last는 (3, 71)로 변경
• 반복 6-2. 새로운 온도가 더 따뜻하기 때문에 last를 pop하고, 결과 배열에 계산해서 업데이트 (3번째 인덱스에 5-3 = 2 업데이트 = 2일 만에 더 따뜻한 날을 만났다는 뜻) -> stack.last는 (2, 75)로 변경
• 반복 6-3. 기존 온도가 더 따뜻하기 때문에 스택에 (5, 72) append

그러면 여기까지 봤을 때, 스택에는 [(2, 75), (5, 72)]가 결과 배열은 [1, 1, 0, 2, 1, 0, 0, 0]으로 되어 있겠다.
*스택에 (2, 75)가 들어있는 것은 2번째 날의 온도보다 아직 더 뜨거운 날을 만나지 못했다는 것을 의미한다고 보면 되겠다.

이후에 이 반복을 계속하다가 6번째 날에 있는 76도를 만나게 되면, "6번째 날 - 2번째 날"을 통해 "2번째 날은 4일 만에 뜨거운 날을 만났다"라는 의미로 값을 업데이트시킬 수 있을 거다.

문제 풀이가 조금 길어졌는데, 차근차근 스택의 원리를 생각해서 풀면 여러분도 풀 수 있을 것이라 생각한다 ^___^

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 571ms (Beats 36.13%), Memory : 26.64MB (Beats 73.72%)

class Solution {
    func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
        var resultTemperatures = [Int](repeating: 0, count: temperatures.count)
        var stack = [(Int, Int)]()

        for (index, temperature) in temperatures.enumerated() {

            // 스택에 값이 있고, 스택의 top값보다 더 뜨거운 온도를 만나면 반복 수행
            while let top = stack.last, top.1 < temperature {
                var compare: (Int, Int)? = stack.popLast()
                
                // 몇 번째 온도는 몇 일만에 더 뜨거운 온도를 만났는지 값을 업데이트
                resultTemperatures[compare!.0] = index - compare!.0
            }
            stack.append((index, temperature))
        }

        return resultTemperatures
    }
}