배열 : 빗물 트래핑(리트코드 42번)

▶ 문제 : https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

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

##### 입력 #####
height = [0,1,0,2,1,0,1,3,2,1,2,1]

##### 출력 #####
6

 

▶ 접근 방법

height 리스트에서 가장 큰 값은 3이다. 
가장 큰 값까지 각각 좌우 최대 높이에서 현재 높이와 차이가 나는 만큼을 더해준다.
좌우 어느 쪽이든 낮은 쪽은 높은 쪽을 향해서 포인터를 가운데 방향으로 점점 옮긴다.
가장 큰 값인 3 지점에서 좌우 포인터가 서로 만나면 값을 리턴한다.

 

▶ 풀이 코드

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

def trap(height: list) -> int:
    if not height:
        return 0
    
    volume = 0
    left, right = 0, len(height) - 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:
            volume += left_max - height[left]
            left += 1
        else :
            volume += right_max - height[right]
            right -= 1
        
    return volume

print(trap(height))