[리트코드] Trapping Rain Water(python)

리트코드, Trapping Rain Water_빗물 트래핑

 

TL;DR

• 투 포인터(two pointer)

문제 분석

1. 0 이상의 정수로 주어지는 높낮이 지도에서 비가 오고 난 이후에 빗방울이 어떻게 튕겼는지 계산하여라.

 

- 1 : 구현해야 하는 문제에 대해서 말하고 있다. 입출력 예시를 살펴보면 문제를 이해할 수 있다.

입출력 형태

입출력 예시

 

- height : 높이가 저장된 배열이다. 주어진 배열을 그림으로 표현하면 예시와 같이 그릴 수 있다.

- 이러한 높낮이로 되어 있는 땅에 비가 내리게 되면 가장 높은 땅인 3에 튕겨서 낮은 쪽으로 빗방울이 흐르게 된다.

  - 가장 높은 3에서 빗방울이 왼쪽으로 튀면, 그 다음 높은 높이인 2까지 총 4개의 빗방울이 고이게 된다.

  - 2에 튀긴 빗방울은 다음 높이인 1까지 흐르게 되고 1개의 빗방울이 고이게 된다.

  - 3에서 빗방울이 오른쪽으로 튀면 다음 높이인 2와 2사이에 1개의 빗방울이 고이게 된다.

  - 따라서 총 6개의 빗방울이 고이게 된다.

풀이

class Solution:
    def trap(self, height: List[int]) -> int:
        # two pointer
        if not height: # height가 비어있다면 0
            return 0
        
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        value = 0
        
        while left < right: # two pointer 종료 조건
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])
            
            # 더 높은 높이에 맞춰서 진행
            if height[left] <= height[right]:
                value += left_max - height[left]
                left += 1
            else:
                value += right_max - height[right]
                right -= 1
                
        return value

 

- 두 개의 포인터를 사용하는 투 포인터(Two pointer)를 활용해서 문제를 풀 수 있다.

- 가장 왼쪽과 오른쪽, 그리고 각 높이를 나타내는 left, right, left_max, right_max를 선언한다.

- 양 극단의 높이를 비교하며, 낮은 쪽이 높은 쪽으로 이동하며, 부족한 만큼의 높이를 채운다.

- 왼쪽과 오른쪽이 교차될 때 종료한다.

  - 예시 1의 일부 대해서 살펴보자.

  - 1. left = 0, left_max = 0, right = 11, right_max = 1, value = 0

        - left가 right보다 작으므로 반복문을 실행한다.

        - left_max와 right_max의 값은 변화가 없다.

        - 왼쪽의 높이 height[left] = 0, 오른쪽의 높이 height[right] = 1. 오른쪽이 더 높으므로 if 문을 실행한다.

        - value = 0, left = 1이 된다.

  - 2. left = 1, left_max = 0, right = 11, right_max = 1, value = 0

        - left가 right보다 작으므로 반복문을 실행한다.

        - left_max의 값이 1이 된다.

        - height[left] == height[right] == 1이므로 if 문을 실행한다.

        - value = 0, left = 2가 된다.

  - 3. left = 2, left_max = 1, right = 11, right_max = 1, value = 0

        - left가 right보다 작으므로 반복문을 실행한다.

        - left_max의 값은 변화가 없다.

        - height[left] == 0 < height[right] == 1이므로 if 문을 실행한다.

        - value = 1 - 0이므로 1이 된다. left = 3이 된다.

  - 이 과정을 반복하게 된다.

개선된 풀이

- 각 높이를 스택의 기준점으로 생각해서 풀 수도 있다.