Trapping Rain Water - LeetCode

문제 풀이 아이디어

순차 탐색?

내가 처음에 떠올린 풀이는 왼쪽부터 탐색을 하다가 기존의 벽 중에 가장 높은 벽 보다 높은 벽이 나오면, (즉 물 웅덩이가 형성되면) 물의 양을 계산하고 다음으로 넘어가는 것이었다.

하지만 이렇게 풀게 되면 문제점이 있다. 바로 오른쪽에 항상 왼쪽이 벽 보다 낮은 벽이 나오라는 법이 없다는 것이다. 아래 주어진 예시를 보자.

높이가 3인 벽이 나올 때까지는 아무런 문제가 없다. 순차 탐색으로도 충분히 물의 높이를 계산할 수 있다. 오른쪽에 무조건 현재까지 가장 높은 벽 보다 높은 벽이 있다고 가정하면 “(현재까지 가장 높은 벽의 높이) - (현재 벽의 높이) = (현재 칸에 고인물)”이 성립하기 때문이다.

하지만 높이가 3인 벽 다음에 있는 벽들 사이에 고이는 물은 구할 수 없다. 현재 벽 보다 오른쪽에 어떤 높이의 벽이 있어 물이 얼마나 고일 수 있는지 알 수 없기 때문이다.

투 포인터!

이렇게 왼쪽, 오른쪽의 양쪽의 벽의 높이 모두 알아야 물의 높이를 구할 수 있는 문제의 경우는 투 포인터로 양쪽 끝에서 부터 가운데로 들어오면서 물의 높이를 구하면 된다.

위 그림을 예시로 들어보자. 위 그림에서 가장 높은 벽은 높이가 3인 벽이다. 왼쪽에서만 진행하는 순차탐색은 가장 높은 벽을 지나가면 물의 양을 구하는 것이 불가능했다. 왜냐하면 가장 높은 벽을 지나가면 물 웅덩이를 만드는 다음 벽의 높이를 알 수 없기 때문이다.

다른 말로 하면 가장 높은 벽까지는 물의 양을 정확하게 구할 수 있다는 것이다. 따라서 왼쪽에서 가장 높은 벽까지 물의 양을 구하고, 오른쪽에서 가장 높은 벽까지의 물의 양을 구해서 더한다면 정확하게 물의 양을 구할 수 있다.

즉 왼쪽에서 “(현재까지 가장 높은 벽의 높이) - (현재 벽의 높이) = (현재 칸에 고인물)”이 성립할 때까지만 물의 양을 구하고 오른쪽에도 마찬가지로 “(현재까지 가장 높은 벽의 높이) - (현재 벽의 높이) = (현재 칸에 고인물)”이 성립할 때까지만 물의 양을 구하면 되는 것이다.

코드

class Solution {
    func trap(_ height: [Int]) -> Int {
        // 벽이 없는 경우 예외처리 (right가 -1인 경우를 방지)
        if height.isEmpty { return 0 }
        
        // 물의 양
        var water = 0
        // 투포인터
        var left = 0, right = height.count - 1
        // 왼쪽에서 가장 높은 벽, 오른쪽에서 가장 높은 벽
        var leftMax = height[left], rightMax = height[right]
        
        // 투포인터가 가운데(= 가장 높은 벽)에서 만날 때까지
        while left < right {
            // 왼쪽 벽이 더 낮으면 왼쪽에서 더 높은 벽을 찾아서 이동
            if height[left] <= height[right] {
                // 현재 칸에 고일 수 있는 물의 양
                water += leftMax - height[left]
                // 포인터 + 1 (오른쪽으로 이동)
                left += 1
                // 왼쪽에서 가장 높은 벽 갱신
                leftMax = max(height[left], leftMax)
            // 오른쪽 벽이 더 낮으면 오른쪽에서 더 높은 벽을 찾아서 이동
            } else {
                // 현재 칸에 고일 수 있는 물의 양
                water += rightMax - height[right]
                // 포인터 -1 (왼쪽으로 이동)
                right -= 1
                // 오른쪽에서 가장 높은 벽 갱신
                rightMax = max(height[right], rightMax)
            }
        }
        
        return water
    }
}