LeetCode 42. Trapping Rain Water

높이가 각각 다른 벽에 물이 얼마큼 차있는지 구하는 문제이다.

---

풀이

투 포인터 사용

투포인터를 사용해서 왼쪽과 오른쪽에서 각각 물을 채우면서 오고, 가장 높은 곳에서 만난다... 라는 사실은 알았지만

어떻게 구현을 해야 할지 감이 안 잡혀서 풀이를 참고하였다.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0

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

        while left < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
            if left_max <= right_max:
                water += left_max - height[left]
                left += 1
            else:
                water += right_max - height[right]
                right -= 1
        return water

먼저 left, right라는 포인터를 각각 선언하고 양 끝에서부터 출발한다.

left_max, right_max 변수는 양 끝에서 출발했을 때 가장 높은 벽을 의미한다.

 

while left < right 는 왼쪽 포인터가 오른쪽 포인터를 넘으면 안 되기 때문에 같을 때까지로 설정하였다.

left_max <= right_max 는 최대 벽 기준 왼쪽 부분에 물을 채우는 상황이다.

water += left_max - height[left] 에서는 가장 높은 왼쪽의 벽을 기준으로 현재의 벽과 만났을 때 얼마 큼의 물이 들어가는지를 계산하여 water에 채운 물을 더한다.

 

그렇게 water에 채운 물을 다 더한 뒤에 반환한다.

결과값

---

Stack을 사용하는 방법도 나와있는데, 몇 번을 봐도 이해가 잘 안 돼서 풀이를 포기했다.

벽의 높이를 stack안에 왼쪽부터 차례차례 담다가 이전에 담긴 것보다 더 높은 벽이 나오면 물을 채우는 방식인데, 아직 이해가 덜 되었다.