[Q. 08] 빗물 트래핑

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

 

이 문제는 투 포인터를 사용하여 해결한다. 투 포인터는 2개의 포인터를 가지고 리스트에 접근하는 알고리즘이다. 보통 조건에 따라 좌/우 포인터를 조작하고 그 행위를 좌측 포인터가 우측 포인터를 넘어갈 때 종료하는 식으로 접근하였던 것 같다. 이 문제 또한 이러한 매커니즘으로 접근해본다.

 

먼저 설정하는 조건은 다음과 같다. 왼쪽에서 설정한 left_max 값이 오른쪽에서 설정한 right_max 값 보다 낮으면 right를 가운데로 당겨오고, 그렇지 않으면 left를 가운데로 당겨가는 식이다.

먼저, left/right 포인터와 초기 left_max/right_max 값을 설정한다.

volume = 0
left, right = 0, len(height)-1
left_max, right_max = height[left], height[right]

 

그 다음 left 포인터 값이 right 포인터 값을 넘어갈 때 까지 다음 행위를 반복한다.

while left < right:
    left_max, right_max = max(left_max, height[left]), max(right_max, height[right])

    if left_max <= right_max:
        volume += left_max - height[left]
        left += 1
    else:
        volume += right_max - height[right]
        right -= 1

 

코드를 보면 left_max와 right_max 값은 현재 포인터의 값과 비교 했을 때 더 큰 값으로 설정한다.

그리고 left_max <= right_max 이면 왼쪽 벽이 오른쪽 벽보 다 높다는 뜻이니 left_max에서 left 포인터가 가리키는 높이의 차이 만큼 volume에 더해주고 left 포인터를 증가시킨다.

그 반대의 경우에는 오른쪽 벽이 왼쪽 벽 보다 높다는 뜻이므로, right_max 에서 right 포인터가 가리키는 높이의 차이 만큼 volume에 더해주고 right 포인터의 값을 증가시킨다.

 

솔직히 문제를 보고 한번에 투포인터 방식을 떠올리기는 힘들다. 그저 많이 접했을 때 투 포인터를 사용해야 되겠다는 느낌이 드는데 이를 실제로 구현하는것도 사실 만만치 않다. 결국 많이 접해보고 다른 사람의 풀이를 보고 내가 직접 다시 구현해보며 익숙해지는 방법 밖에는 없는 것 같다.

 

전체 코드는 다음과 같다.

class Solution:
    def trap(self, height: List[int]) -> int:
        
        volume = 0
        left, right = 0, len(height)-1
        left_max, right_max = height[left], height[right]

        while left < right:
            left_max, right_max = max(left_max, height[left]), max(right_max, height[right])

            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1

        return volume