Python 알고리즘 인터뷰 - 문제8 빗물트래핑

42. leetcode Trappong Rain Water

 

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

예제1

입력

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

 

출력

6

 

 

풀이

빗물은 가운데를 기준으로 양쪽에서 기둥의 높이가 작은 쪽을 기준으로 쌓인다. 가운데 기둥이 크기와는 상관 없이 양쪽 기둥의 높이에 따라 빗물의 높이가 결정되는 것이다. 이 문제를 풀기 위해 다음 순서대로 빗물이 쌓이는 순서를 정리해본다.

 

기둥 크기 배열을 heights라 하고 양쪽 기둥의 위치를 각각 L, R이라고 한다. h[L], h[R] 크기를 max_L, max_R에 저장한 후 양쪽 기둥 중에서 작은 쪽의 기둥을 방향에서 높은 기동 방향으로 순차적으로 기둥의 높이를 계산하며 빗물을 채워나간다.

다음과 같이 max_L < max_R인 경우 L->R 방향으로 빗물을 채워나간다.

max_L < max_R인 경우 L->R 방향으로 빗물 높이를 계산

만약 L~R 사이 기둥의 높이가 max_L보다 작다면 각 빗물의 높이는 다음과 같이 max_L 보다 작은 값으로 채워진다.

L~R 기둥 사이의 기둥의 높이가 max_L보다 작은 경우

L->R 방향으로 진행 중 heights[L] > max_L인 기둥이 존재할 경우에는 max_L값을 갱신하고 갱신된 max_L 값을 기준으로 같은 방향으로 빗물 값을 계산해 나간다. 

L->R 진행 중 heights[L] > max_L을 만난 경우

 

heights[L] > max_R인 기둥을 만난 경우 빗물은 더 이상 왼쪽 기둥을 기준으로 채워지지 않고 높이가 더 작은 오른쪽 기둥을 기준으로 채워지게 된다. R->L 방향으로 빗물을 채워나간다.

L->R 진행 중 heights[L] > max_R인 경우 R->L로 방향 전환

 

동일하게 R->L 진행 중 height[R] > max_L인 경우 L->R 방향으로 진행한다. 

R->L 진행중 heights[R] > max_L인 경우 다시 L->R로 방향 전환

 

빗물의 총량을 volume이라고 했을 때 진행 방향별 volume은 다음과 같이 계산하고

#L->R 방향일 경우
volume += max_left - height[L]

#R->L 뱡항일 경우
volume += max_right - height[R]

max_L, max_R 크기에 따라 다음 코드에 따라 volume 계산 및 좌, 우 포인터 위치를 이동한다.

if max_left <= max_right:
	#L->R 방향일 경우
	volume += max_left - height[left]
    left += 1
else:
	#R->L 뱡항일 경우
	volume += max_right - height[right]
    right -= 1

 

이렇게 빗물을 채워가는 것을 L < R이 될 때까지 반복하며, 전체 코드는 다음과 같다.

 

전체 코드

def trap(self, height):
    left, right = 0, len(height) - 1
    max_left = max_right = 0
    volume = 0
    while left < right:
        max_left = max(max_left, height[left])
        max_right = max(max_right, height[right])
        if max_left <= max_right:
            volume += max_left - height[left]
            left += 1
        else:
            volume += max_right - height[right]
            right -= 1

    return volume

 

빗물의 총량을 volume으로 하였으며, 진행 방향에 따라 max_left - height[left], max_right - height[right]값을 더하여 구하였다.