리트 코드 빗물 트래핑

리트 코드 빗물 트래핑

빗물 트래핑

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

• 입력

[0,1,0,2,1,0,1,3,2,1,2,1]

• 출력

6

이 문제의 핵심은 투 포인터이다. 투 포인터를 양쪽 끝에서 점점 가운데로 보내면 결국 가장 높은 곳에서 포인터가 만나게 된다.

그리고 left와 right 각각의 max값을 매번 갱신하며 max값에서 현재값을 뺀 것을 volume에다 더한다.

코드를 살펴보면

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

우선 left는 0, right는 마지막 인덱스값을 기본값으로 갖는다. 그리고 left_max와 right_max는 각각 height[left], height[right]를 갖는다. volume은 0을 대입해준다.

그 후 두 포인터가 만나면 끝난다는 가정하에 while left<right:으로
반복문을 진행한다.

left_max = max(height[left], left_max) 이 코드에서 left_max값을 매번 초기화 시켜준다. left_right도 마찬가지로 초기화 시킨 다.

그 후 left_max < right_max를 넣어 right_max가 최댓값에 도달했다면 left 포인터가 계속 이동하도록 한다.

그 후 volume += left_max - height[left]를 이용해 left_max와 현재값의 차이로 volume에 빗물의 양을 더한다.

그리고 left+=1로 포인터를 이동시킨다. 마찬가지로 right도 동일한 알고리즘으로 이동하고 두 포인터가 만나게 되면 반복문은 끝이난다.

출처: 파이썬 알고리즘 인터뷰 (박상길 지음)