Trapping Rain Water (Two Pointers)

LeetCode의 Trapping Rain Water 문제다.

Trapping Rain Water - LeetCode

처음으로 건드려보는 Hard 난이도의 문제다. 사실 Medium 문제도 혼자 힘으로 풀기 버거워서 Hard 난이도는 손대지 않고 있었는데 책에서 풀이를 알려주기 때문에 이를 공부하는 셈 치고 풀어보았다. 사실 직접 푼 것도 아니고 해설을 읽고 분석하는 정도지만 나중에 비슷한 문제가 나왔을 때 활용할 수 있을 것이다.

 

문제에서는 x축 방향으로 나열된 y축 값이 배열에 담겨 주어진다. 즉 [3, 2, 1, 5, 4]처럼 배열이 주어졌을 때 이는 다음과 같은 도형을 나타낸다.

이런 도형에 비가 내렸을 때 2차원 평면상에 얼마나 많은 칸에 빗물이 담길 수 있는지를 계산하는 문제다. 위의 도형 같은 경우 아래 그림처럼 빗물이 담길 것이다.

총 3칸에 빗물이 들어찰 수 있기 때문에 3을 반환해주면 된다. 맨 왼쪽과 오른쪽에는 따로 벽이 없기 때문에 빗물이 흘러내려서 담을 수 없다. 이것 말고는 별다른 조건이 없기 때문에 언뜻 보면 간단해 보이지만 어떻게 프로그램으로 구상해야 할지 감이 잘 잡히지 않는다. 책에서는 두 개의 포인터를 이용하여 양쪽에서 가운데로 좁혀오면서 탐색하는 풀이를 제공하고 있다.

 

빗물을 담을 수 있는 공간이란 건 무엇일까? 위의 그림에서는 왼쪽 막대와 오른쪽 막대로 막혀있는 공간일 것이다. 그러나 문제에서 주어지는 도형은 항상 대칭인 것은 아니기 때문에 어느 막대부터 어느 막대까지 빗물을 담을 수 있는지 파악하기가 까다롭다. 도형 구조에 따라 아예 빗물을 담을 공간이 없는 경우도 있을 것이다.

그래서 기본적으로 생각해볼 수 있는 방법은 한쪽 끝의 막대부터 시작해서 자기 막대보다 낮은 막대가 나오면 그 차이만큼 물을 담을 수 있는 공간으로 보는 것이다. 예를 들어 위의 그림 같은 경우 첫 번째(왼쪽) 막대의 높이는 1이다. 그 오른쪽 막대는 없기 때문에 높이가 0이며 첫 번째 막대보다 낮기 때문에 1 - 0, 즉 1셀만큼 빗물을 담을 수 있다. 그리고 그 오른쪽 막대는 높이가 첫 번째 막대와 같기 때문에 빗물을 담을 수 없다.

 

그럼 이제 높이가 2인 네 번째 막대부터는 어떻게 해야 할까? 이 경우 지금 빗물을 담을 수 있는 기준으로 삼고 있는 첫 번째 막대보다 높기 때문에 현재 기준으로 잡고 있는 막대를 이 네 번째 막대로 업데이트한다. 그래서 이제 빗물을 담을 수 있는 기준은 막대의 높이가 2보다 작은 경우로 업데이트된다. 그에 따라 다섯 번째, 여섯 번째 막대는 높이가 1이기 때문에 1셀씩 추가되어 현재 도형에는 총 3셀에 빗물을 담을 수 있다고 계산할 수 있다. 그러면 이렇게 한 번만 확인하면 끝나는 것일까? 하지만 이 로직은 아래와 같은 경우를 처리할 수 없다.

즉 처음 기준으로 잡은 왼쪽 막대에 비해 모든 오른쪽 막대가 기준 막대보다 낮은 높이일 경우 물을 담을 수 없다. 위의 로직에서는 기준 막대와 지금 탐색하고 있는 막대의 높이 차이를 계산하기만 하지 이 기준 막대의 끝까지 물을 담을 수 있는지 아닌지는 확인하고 있지 않기 때문이다. 위의 도형 같은 경우 로직대로라면 총 22칸의 빗물을 담을 수 있다. 하지만 실제로 빗물을 담을 수 있는 공간은 아래와 같다.

당연하지만 2차원상에서 뭘 담으려면 양쪽이 막혀있어야 하는데 왼쪽 막대는 높이가 5, 오른쪽 막대는 높이가 3이기 때문에 더 낮은 쪽에 기준을 맞춰야 한다는 것이다. 그렇다면 기준 막대를 왼쪽 막대가 아닌 오른쪽 막대부터 설정해서 탐색해보면 어떨까? 이 경우 자신의 높이에 알맞게 탐색할 수 있다.

그럼 상황에 따라 왼쪽 막대부터 기준을 잡거나 오른쪽 막대부터 기준을 잡아가면서 탐색하는 방법으로 구현해야 할까? 하지만 아래처럼 두 방법 모두에서 문제를 일으킬 수 있는 경우가 존재한다.

그건 바로 위처럼 제일 높은 막대가 왼쪽 끝이나 오른쪽 끝이 아닌 한가운데 존재하는 경우다. 맨 처음 로직인 왼쪽 막대부터 기준을 잡아서 탐색하는 방식의 경우 세 번째 막대까지는 빗물을 담을 공간을 잘 파악할 수 있다. 그러나 네 번째 막대에서 기준 막대의 높이가 5로 상승한 이후에는 이전과 같은 문제가 발생하고 있다.

반대로 오른쪽 막대부터 기준을 잡아서 탐색하는 방식의 경우 역시 동일한 문제가 발생한다. 그런데 왼쪽 막대의 실행 결과와 비교해보면 2, 3번째 막대와 5, 6번째 막대에 빗물을 담는 부분이 공통되는데 그럼 왼쪽 막대의 실행 결과와 오른쪽 막대의 실행 결과 중 공통되는 부분을 찾아서 계산하면 되지 않을까? 하지만 실행 결과에서 일일이 공통되는 부분을 찾기보다 각 탐색 시 적절한 곳(위의 도형에서는 4번째 막대)까지만 탐색하고 그 결과를 합치는 방법을 생각해볼 수 있다.

 

지금 탐색에서 문제가 되는 점은 빗물을 담을 수 있는 공간을 제대로 파악하고 있지 못한다는 것이다. 빗물을 담을 수 있는 공간이란 왼쪽과 오른쪽 막대의 높이가 같아야 하며 한쪽 막대가 더 높은 경우 낮은 쪽을 기준으로 빗물이 담긴다는, 현실에서도 당연한 특징이 있다. 위의 로직에서는 어떤 높은 막대를 만난 후 자신과 같거나 더 높은 막대를 만나지 못했기 때문에 제대로 탐색하지 못하고 있다. 그럼 주어진 막대 중 가장 높은 막대까지만 탐색하면 되는 게 아닐까?

위의 그림처럼 가장 높은 막대까지만 탐색했을 경우 왼쪽 막대부터 시작하는 탐색과 오른쪽 막대부터 시작하는 탐색이 각각 두 셀 씩 계산한다. 이를 합산하면 총 4개의 셀에 빗물을 담을 수 있다는 것이 되며 이는 문제에서 요구하는 답과 일치한다. 그렇다면 더 위의 예제에도 적용해보면 어떨까?

왼쪽 막대부터 탐색하는 경우 제일 왼쪽 막대가 제일 높은 막대기 때문에 시작하자마자 탐색을 중단한다. 그리고 오른쪽 막대는 높이가 3인 7번째 막대를 기준 막대로 삼아 탐색을 시작해서 자신보다 낮은 막대들과 차이를 빗물로 담을 수 있는 공간으로 계산하며 왼쪽으로 탐색한다. 물론 탐색 도중에 현재 기준 막대보다 높은 막대면서 제일 높은 막대가 아닌 막대를 만나는 경우 기준 막대를 해당 막대로 업데이트해야 할 것이다.

하지만 모든 막대의 높이가 유일(unique)하다는 보장이 없기 때문에 제일 높은 막대가 여러 개 있을 수 있다. 이 경우 왼쪽과 오른쪽 끝에서 탐색하다가 제일 높은 막대를 만나면 탐색이 멈추기 때문에 이 막대들 사이에 있는 공간은 측정하지 못한다는 단점이 있다. 그래서 이를 해결하는 방법이 책에서 설명하는 두 개의 포인터를 이용한 방식이다.

투 포인터를 사용하는 방식은 이 도형을 왼손과 오른손으로 감싸면서 점점 좁혀오는 방식이라 할 수 있다. 즉 두 막대 중 더 큰 쪽으로 탐색하다가 탐색 인덱스(왼쪽은 Left Index이며 0, 오른쪽은 Right Index이며 배열의 크기 - 1부터 시작)가 역전됐을 경우 탐색을 중단하는 것이다. 그리고 매 탐색마다 현재 탐색하고 있는 막대와 지금까지 탐색된 막대 중 제일 높은 막대, 즉 기준 막대의 높이를 비교해서 기준 막대를 업데이트해야 한다. 맨 처음에는 지금 발견된 막대가 제일 높은 막대기 때문에 위의 도형에서 왼쪽(Left Max Height), 오른쪽 기준 막대(Right Max Height)는 각각 2의 높이를 가진다.

이제 두 방향(왼쪽, 오른쪽) 중 어느 쪽으로 탐색할지 정해야 한다. 여기서는 왼쪽 기준 막대가 오른쪽 기준 막대보다 작거나 같다면 오른쪽으로 탐색하고 그렇지 않다면 오른쪽 기준 막대에서 왼쪽으로 탐색하는 것을 원칙으로 한다. 지금은 왼쪽 기준 막대와 오른쪽 기준 막대의 높이가 같기 때문에 왼쪽 기준 막대에서 오른쪽으로 먼저 이동하며 현재 막대(인덱스 1의 높이 1)와 왼쪽 기준 막대(인덱스 0의 높이 2)의 차이만큼 빗물을 담을 수 있는 공간으로 판단한다.

그다음 탐색에서는 왼쪽 기준 막대보다 높은 막대를 탐색했기 때문에 왼쪽 기준 막대(인덱스 0의 높이 2)가 현재 막대(인덱스 2의 높이 5)로 업데이트된다. 그리고 이제는 왼쪽 기준 막대가 오른쪽 기준 막대보다 높기 때문에 오른쪽 막대에서 왼쪽으로 탐색을 시작한다.

이전과 동일하게 현재 탐색하는 막대가 기준 막대보다 낮을 경우 빗물을 담을 수 있는 공간으로 파악한다.

그리고 그다음 탐색에서는 현재 기준 막대(인덱스 6의 높이 2) 보다 높은 막대(인덱스 4의 높이 5)를 발견했기 때문에 기준 막대를 업데이트한다. 결과적으로 두 기준 막대가 둘 다 제일 높은 막대에 도달했다. 이전처럼 단순히 제일 높은 막대까지만 탐색하도록 하면 인덱스 3의 빗물 공간을 파악하지 못하기 때문에 이 로직에서는 왼쪽이나 오른쪽 기준 막대가 반대쪽 기준 막대와 같거나 낮을 때 탐색하도록 구현해야 한다.

어느 방향이던 상관없지만 왼쪽 기준 막대가 오른쪽 기준 막대와 같거나 낮을 때 오른쪽으로 탐색하는 방식으로 구현했다면 현재 두 기준 막대가 같은 높이기 때문에 다음처럼 왼쪽에서 오른쪽으로 탐색하게 된다. 그래서 왼쪽 기준 막대의 높이 5와 현재 막대의 높이 1의 차이만큼 빗물을 담을 수 있는 공간으로 판단한다. 그리고 한번 더 탐색하면 왼쪽 탐색 인덱스(4)가 오른쪽 탐색 인덱스(4)보다 작지 않기 때문에 도형의 모든 부분을 탐색한 것으로 판단하고 탐색을 종료하는 것이다.

이런 탐색법을 사용하면 위와 같은 도형도 문제가 없다. 물론 위 도형은 빗물을 담을 공간이 없는데 왼쪽 기준 막대는 인덱스 0의 높이 1보다 낮은 막대가 나오지 않기 때문에 공간을 파악하지 않으며 오른쪽 기준 막대는 인덱스 6의 높이 3이 왼쪽 기준 막대의 높이보다 항상 크기 때문에 왼쪽으로 한 번도 탐색하지 않는다. 그러므로 이 도형은 빗물을 담을 공간이 없다고 파악하는 것이다.

 

이를 기반으로 구현한 로직은 다음과 같다.

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 1:
            return 0
        
        index_left, index_right = 0, len(height) - 1
        max_height_left, max_height_right = height[index_left], height[index_right]
        rain_cells = 0
        
        while index_left <= index_right:
            if max_height_left <= max_height_right:
                max_height_left = max(max_height_left, height[index_left])
                rain_cells += max_height_left - height[index_left]
                index_left += 1
            else:
                max_height_right = max(max_height_right, height[index_right])
                rain_cells += max_height_right - height[index_right]
                index_right -= 1
        
        return rain_cells      

높은 성능의 풀이를 확인해도 이와 비슷한 로직을 사용한 것을 볼 수 있다.

 

LeetCode에서 제공하는 풀이는 이것 말고도 브루트 포스, 다이나믹 프로그래밍, 스택을 이용한 풀이가 있다. 이는 추후 다루겠다.