[Leetcode/Hard] 빗물 트래핑 (42. Trapping Rain Water, Swift)

https://leetcode.com/problems/trapping-rain-water/description/

 

🤔 문제 설명

각 막대의 너비가 1인 높이를 나타내는 음이 아닌 정수 리스트가 주어지면, 비가 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하세요.

검은 부분이 막대, 파란 부분이 빗물을 의미 -> 여기서는 빗물 6개가 갇힘

height = [0,1,0,2,1,0,1,3,2,1,2,1]
// 6

 

💡 풀이

예전 수학 문제에서 이와 비슷한 문제를 본 경험이 떠올랐다.

문제를 해결하기 위해 생각한 방법은 두 가지였다.
하나는 양끝 지점에서 최댓값을 유지하며 좁혀 들어오는 방법, 또 하나는 앞에서부터 쭉 최댓값을 유지하며 값을 채우는 방법

나는 이 중에서 전자의 방법을 사용했다. 전문 용어로 이렇게 양 끝 지점에서 범위를 갈수록 줄이는 방법을 "투 포인터"라고 부른다.

일단, 그전에 height이 아무것도 없을 경우에 0으로 예외처리를 먼저 해줘야 한다.
volume이라는 변수에 채울 수 있는 물 값을 계속 더해갈 것인데, 최댓값을 계속 저장해두면서 그 최댓값보다 부족한 값을 계속 더해가면 된다.

 

🧑🏻‍💻 코드 (Swift ver.)

Runtime : 32ms (Beats 39.24%), Memory : 16.01MB (Beats 39.72%)

class Solution {
    func trap(_ height: [Int]) -> Int {
        var water = 0
        
        var left = 0
        var right = height.count-1

        var leftMax = height[left]
        var rightMax = height[right]

        while (left < right) {
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])

            if (leftMax < rightMax) {
                water += leftMax - height[left]
                left += 1
            } else {
                water += rightMax - height[right]
                right -= 1
            }
        }

        return water
    }
}