LeetCode - The World's Leading Online Programming Learning Platform

문제 해결 아이디어

순서 중요 + 필터링 = Stack

문제의 조건을 살펴보면 어떤 날보다 따뜻한 날을 현재 보다 미래, 즉 Array 안에서 다음 Element에서 찾아야 한다. 그리고 현재보다 추운 날은 빼고 따뜻한 날만 찾아야 한다. 즉 순서가 중요한 필터링 작업을 해야 한다. 이럴 때 가장 효과적인 자료구조는 Stack이다.

Stack에 index를 push하자.

이 문제가 다른 Stack 문제와 다른 점은 단순하게 필터링을 하는 것이 아니라 현재 날보다 따뜻한 날이 나오면 그 날이 현재를 기준으로 얼마나 떨어져있는지를 알아야 한다는 점이다. 따라서 Stack에는 index를 저장하는 것이 좋다. temperatures 배열은 index의 차이가 날짜의 차이이기 때문이다.

“미래의 더 따뜻한 날” 찾기 → ”과거의 더 추운 날” 찾기

이 문제를 “미래의 더 따뜻한 날”을 찾는다는 방식으로 접근하면 어려워진다. 반대로 현재보다 “과거의 더 추운 날”을 찾는다는 개념으로 접근하는 것이 오히려 이해하기 쉽다. Stack 안에 현재보다 “과거의 더 추운 날”이 있다면 pop한다. 그리고 그 pop한 날짜와 현재 날짜의 차이를 pop한 날짜의 답에 저장한다.

나머지 설명은 코드와 주석으로 갈음한다.

코드

class Solution {
    func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
        // 정답 배열: 선형적으로 정답을 저장할 수 없고 index로 저장해야하므로 기본값을 넣어놓는다.
        var ans = Array(repeating: 0, count: temperatures.count)
        
        // index를 저장해둘 배열
            // stack에는 아직 더 높은 온도를 찾지 못한 날의 index가 들어있다.
            // 즉 미래에 온도가 더 높은 알이 나오면 pop
        var stack = [Int]()
        
        for (i, t) in temperatures.enumerated() {
            // stack의 마지막 날이 현재 온도보다 낮으면 = 더 따뜻해진 날을 찾으면 pop
            while !stack.isEmpty && t > temperatures[stack.last!] {
                let pop = stack.popLast()!
                ans[pop] = i - pop // index 차이 (= 날짜 차이)를 저장
            }
            // stack에 push
            stack.append(i)
        }
        
        return ans
    }
}