[Leetcode] two pointer 를 사용한 Trapping rain water 풀이

투포인터를 이용한 문제를 풀어보자. 투포인터를 구현하는 방식에는 여러가지가 있지만, 대개는 시작점과 끝점 또는 왼쪽/오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략을 말한다. 범위를 좁혀가기 위해서는 대체로 배열이 정렬되어 있어야 한다. 투 포인터또한 배열을 순차적으로 접근한다는 점에서 브루트 포스와 비슷한거 아닌가? 라는 생각을 잠깐 했지만, 브루트 포스가 2중 포문으로 타임아웃 땅땅 내려준다면 투포인터는 훨씬 향상된 시간복잡도를 보여준다. 모든 원소에 접근하긴 하지만, On^3 의 브루트포스 결과를 On^2 으로 개선할 수 있는 것이다. 

 

1. Trapping rain water 

리트코드의 빗물트래핑 문제로, 파이썬 알고리즘 인터뷰 책을 참고했다.

처음 봤을 때 브루트포스 방식은 쉽게 이해갔지만 투 포인터 문제 설명이 이해가지 않아서 잠깐 골몰하다 다음 문제부터 풀어볼까? 했는데 3Sum(마찬가지로 투포인트 방식으로 풀이한다.)가 나와서 투포인터 개념을 제대로 이해하고 넘어가야지 싶었다.

개념 자체는 어렵지 않은데, 이걸 내가 문제풀이를 위해 처음부터 생각해낼 수 있느냐? 하면 아니였다. 역시 훈련이 답이다 .. ^^

문제는 다음과 같다. 

 

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

입출력

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

쉽게 말하자면, 검은 부분이 벽돌이고 벽돌 높이를 인자로 받아 그 틈으로 얼마나 많은 빗물이 고일 수 있는지를 리턴하는 문제이다. (단위는 블록이다.) 

 

 

제한사항

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

( 출처 : https://leetcode.com/problems/trapping-rain-water/submissions/ )

class Solution:
    def trap(self, height: List[int]) -> int:
        # Using two pointer
        
        if not height:
            return 0
        
        volume = 0
        
        # design left pointer and right pointer 
        left, right = 0, len(height) - 1
        left_max, right_max = height[left] , height[right]
        
        # when right is bigger than left 
        while left < right:
            left_max , right_max = max(height[left], left_max),max(height[right], right_max)
            
            # move to higher inflection point_ which pointer should be move?
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
            
        return volume

우선 투 포인터는 최대로 이동시켜야 한다. 즉 가운데를 기준으로 가장 외곽으로 보낸다. 가운데 가장 높은 최대 벽돌 높이를 standard 로 가정한다. (책에서는 최대 높이라고 표현했는데, 나는 기준이라고 이해했다.)  기준점을 향해 가장 외곽에 있는 포인터들은 이동한다. 

 

위의 코드를 자세히 설명하자면, 우선 if not height라는 가정으로 예외를 처리한다. 이 후 volume 변수를 선언하는데, volume은

inflection point(변곡점)에서 직전 벽돌의 높이를 뺀 값으로 물의 높이라고 생각하면 된다. 

 

이 후 왼쪽/ 오른쪽 포인터를 지정하고 그 중 최댓값들을 선언한다.

기준점 (최대 높이의 벽돌) 까지 각각 좌우 벽돌 최대 높이 left_max, right_max가 현재 높이와의 차이만큼 물 높이 volume 을 더해 나간다. 좌우 어느 쪽이든 낮은 쪽은 높은 쪽을 향해서 포인터가 가운데로 이동하게 되고 마지막엔 기준점에서 두 포인터가 만나게 된다. 이 방식은 O(n)으로 풀이가 가능하다. 

 

그리고 책에서는 이 문제를 스택을 이용하여 풀이하기도 한다. 스택에 인자를 차례대로 쌓고, 현재 높이가 이전 높이보다 높을 때 , 변곡점을 기준으로 격차만큼 volume을 채운다. 이전 높이는 고정된 형태가 아니라 들쑥날쑥하기 때문에, 계속 스택으로 채워 가다가 변곡점을 만날 때마다 스택에서 하나씩 꺼내면서 이전높이와의 차이만큼 volume에 더한다. 이 포스팅의 주제는 투 포인터이기 때문에 여기서 스택을 이용한 풀이를 다루진 않지만, 다음 포스팅은 스택을 주제로 문제를 모아봐야겠다.