[leetcode 42] Trapping Rain Water - hard

오늘은 리트코드(leetcode) 42번 문제 trapping rain water에 관해 풀어보겠습니다. 

(링크: https://leetcode.com/problems/trapping-rain-water/description/)

 

 

문제는 높이를 입력받아 비 온 뒤 얼마나 많은 물이 쌓일 수 있는지 계산을 요구하는 문제입니다.

 

이 문제는 높이와 너비 모든 공간을 차례대로 살펴보면서 풀어나간다면 $O(n^2)$만큼의 시간 복잡도로 풀이가 가능합니다.

하지만 시간 복잡도가 높기 때문에, 더 효율적인 풀이를 찾는 것이 권장됩니다.

 

풀이: 투 포인터 활용

투 포인터를 활용하면 $O(n)$의 시간 복잡도로 문제를 풀 수 있다고 생각했습니다.

우선 다음 그림을 보겠습니다.

위 그림에서 주목할 부분은 '가장 높은 막대'입니다. 

최대 높이는 3입니다.

가장 높은 막대의 높낮이는 전체 부피에 영향을 끼치는 요소로 생각할 것이 아닌, 그저 왼쪽과 오른쪽을 가르는 장벽으로 생각하면 됩니다.

 

투 포인터의 메커니즘은 다음과 같습니다.

• 각각 왼쪽 끝과 오른쪽 끝에서 포인터가 이동하면서 높이를 스캔합니다.
• 최대 높이의 막대까지 각각 좌우 기둥 최대 높이 (left_max, right_max)가 현재 높이와의 차이만큼 물 높이(volume)를 더해 나갑니다

이를 코드로 간단하게 살펴보자면, 다음과 같은 코드 조각을 구성할 수 있습니다.

volume += left_max - height[left]
...
volume += right_max - height[right] 



if left_max <= right_max:
    volume += left_max - height[left]
    left += 1
else:
    volume += right_max - height[right]
    right -= 1

 

이 경우 적어도 좌/우 낮은 쪽은 항상 그만큼 채워질 것이기 때문에, 어느 쪽이든 낮은 쪽은 높은 쪽을 향해서 포인터가 가운데로 이동하게 됩니다. (left += 1 or right -= 1)

 

간단하게 정답 코드를 공유하면서 그림을 통한 각 iteration 별 어떻게 포인터가 움직이는 지 추가적으로 알아보겠습니다.

 

Solution

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        volume = 0
        l, r = 0, len(height) - 1  # init. two pointer
        lmax, rmax = height[l], height[r]

        while l < r:
            lmax, rmax = max(height[l], lmax), max(height[r], rmax)

            if lmax <= rmax:
                volume += lmax - height[l]
                l += 1
            else:
                volume += rmax - height[r]
                r -= 1

        return volume

 

 

위 코드에서 height가 없을 경우 0을 반환하는 부분은 따로 설명하지 않겠습니다

 

최초 두 개의 포인터의 위치를 정해줍니다 ---->  l, r = 0, len(height) - 1

 

이후에 좌측의 가장 큰 높이와 우측의 가장 큰 높이를 설정해야 하는데, 현재 데이터는 우리가 갖고 있는 포인터의 위치밖에 없기 때문에 해당 값으로 초기화를 시켜줍니다.  lmax, rmax = height[l], height[r]

Iterations

매 iteration에서 각 변수의 값은 다음과 같습니다. 매 iteration에서 좌측과 우측에서 확인된 최대 높이 값에 따라 l += 1  또는  r -= 1 처럼 포인터의 이동이 다르다는 점을 유의하시면서 살펴 보시면 됩니다.

	l	lmax (=height[l])	r	rmax (=height[r])	lmax <= rmax	volume	cum volume
step 1	0	0	11	1	True	0	0
step 2	1	1	11	1	True	0	0
step 3	2	1	11	1	True	1	1
step 4	3	2	11	1	False	0	1
step 5	3	2	10	2	True	0	1
step 6	4	2	10	2	True	1	2
step 7	5	2	10	2	True	2	4
...	...	...	...	...	...	...	...

 

프로세스에 대해 그림을 따로 첨부하진 않았으나, 그림을 확인하면서 풀어보시면 더 이해하기 쉽지 않을까 생각합니다.