Trapping Rain Water[leetcode 42]

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

 

Problem.

각 막대의 너비가 1인 고도 지도를 나타내는 음이 아닌 정수 n이 주어지면 비가 내린 후 얼마나 많은 물을 가둘 수 있는지 계산해라

 

 

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: 위의 지도(검은색 부분)는 배열 [0,1,0,2,1,0,1,3,2,1,2,1]로 표시됩니다. 이 경우 빗물 6개(파란색 부분)가 갇혀 있습니다.

 

 

Solution.

이 문제를 해결하기 위해 "Two Pointers" 방법을 이용할 수 있다.

투 포인터는 배열에서 여러가지 쌍을 검색하는 데 일반적으로 사용된다. 만약 자세한 내용을 알고싶다면 geeks 내용을 살펴보자. https://www.geeksforgeeks.org/two-pointers-technique/

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        water = 0
        
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    water += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    water += right_max - height[right]
                right -= 1
        
        return water

 

1. height가 비어있는지 확인하고 비어있다면 0을 반환.

2. 두 개의 포인터 left, right를 사용하며, left는 시작, right는 끝을 의미한다.

3. left_max와 right_max 변수를 통해 각각 왼쪽 및 오른쪽에서 최대 높이를 추적

4. water 변수를 사용해 총 물의 양 계산

5. left가 right보다 작은 동안 반복

   - height[left] 가 height[right] 보다 작다면?

        - height[left]가 left_max보다 크거나 같으면, left_max를 업데이트

        - 아니라면, left_max - height[left]만큼의 물을 water에 더합니다.

        - left를 1 증가시킵니다.

   - height[right]가 height[left]보다 작거나 같다면?

        - height[right]가 right_max보다 크거나 같으면, right_max를 업데이트

        - 그렇지 않으면, right_max - height[right]만큼의 물을 water에 더합니다.

        - right를 1 감소시킵니다.

6. water 반환

 

이 알고리즘은 O(n) 으로 동작하며 n는 height 리스트 길이