leetcode : Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

 

리트코드에서 엄청 유명한 문제중 하나

예전에 한 번 풀어봐서 two pointers 문제라는걸 알고 풀었는데도 상당히 어렵다..

 

이건 채워질 물의 양을 수직으로 쪼개서 생각하는게 필요하다 (난 수평으로 쪼갤 생각은 해봤는데 왜 수직으로 쪼갤생각을 안해봤는지..)

자 그러면 i번째 칸에 채워질 물의 양은 어떻게 구하지?

딱 i번째 칸 기준으로만 생각해보자.

i번째 칸에 물이 1이라도 채워지려면 왼쪽, 오른쪽 모두에 height[i]보다 큰 기둥이 무조건 있어야 한다. 아니면 물이 흘러버려서 못고이니까.

그럼 i번째 칸에서 왼쪽을 봤을때 가장 큰 기둥의 높이를 leftmax(i)

오른쪽을 봤을때 가장 큰 기둥의 높이를 rightmax(i)라고 하자

물은 두 높이중 더 낮은 높이까지만 차는게 최대이므로 min(leftmax(i), rightmax(i))가 현재 i에서 물이 차오를 수 있는 최대 높이다.

근데 i번째 칸에는 height[i]높이의 기둥도 있을것이므로 물이 찰 수 있는 양은 min(leftmax(i), rightmax(i)) - height[i]

i번째 기둥이 가장 높은 기둥이면 min(leftmax(i), rightmax(i))이 height보다 낮게 나올것이다. 그럼 물이 차는 양이 음수가 되니까 최종적으로 i번째 칸에 찰 수 있는 물의 양을 구하려면 max(0, min(leftmax(i), rightmax(i)) - height[i])

 

정말정말 naive하게 생각하면 i를 0부터 끝까지 스캔하면서 각 i에대해 왼쪽, 오른쪽으로 스캔을 진행해 큰기둥을 찾아야 한다.

그럼 O(N * (2 * N)) = O(N^2)의 시간복잡도가 나오겠지.

근데 잘 생각해보면 그럴 필요가 없다. 예를들어

10 1 1 1 1 1 1

기둥이 이렇게 있으면

두번째부터 끝까진 leftmax가 다 10이잖아?

leftmax값을 한 변수에 담아서 최대값으로 계속 갱신해주면서 스캔하면 된다. O(N) 스캔으로 모든 기둥의 leftmax값을 다 알수있다.

leftmax, rightmax 구하고 각 기둥에서 담을수있는 물을 다 더하면 3*N, 그러니까 O(N)

 

class Solution:
    def findmax(self, height, left):
        result = [-1] * len(height)
        
        maxval = 0
        for i in range(len(height)-1 if left else 0, -1 if left else len(height), -1 if left else 1):
            result[i] = maxval
            maxval = max(maxval, height[i])
            
        return result
    
    def trap(self, height: List[int]) -> int:
        answer = 0
        
        rightmax = self.findmax(height, False)
        leftmax = self.findmax(height, True)

        for i in range(len(height)):
            answer += max(0, min(maxright[i],maxleft[i]) - height[i])
        
        return answer

 

다만 이렇게 하면 공간복잡도가 O(N)이다. 아 물론 정답값이 list니까 공간복잡도는 무조건 O(N)이긴 한데 정답값을 담을 변수를 제외한 공간의 복잡도가 O(N). 이마저도 최적화 할 수 있는 방법이 있다.

 

특정 지점의 leftmax와 rightmax를 O(1) space로 알 수 있는 방법이 있을까?

여기서 two pointers 개념이 등장한다.

left pointer(이하 lp)를 0부터, rp를 length-1부터 각각 오른쪽, 왼쪽으로 스캔해간다.

이렇게 어떻게 구하냐고?

 

사실 우리가 궁금한건 leftmax, rightmax가 아니다. 왼쪽, 오른쪽으로 (나보다 큰 기둥들 중 최소값)이 궁금한거다.

나보다 큰 기둥들 중 최대값이 아니라 최소값이다. 이 최소값에 집중하면 문제를 풀수있다.

일단 lp와 rp를 움직여가면서 leftmax와 rightmax는 갱신할수있을것이다.

lp를 2까지 움직이고 rp를 8까지 움직여서 leftmax,rightmax값을 갱신했다고 치자.

우린 특정지점(i=3 혹은 i=7)에서 물이 얼마나 찰 수 있는지 구할 수 있는가? 구할수있다. leftmax<rightmax니까 leftmax-height[i]로 구하면 된다.

왼쪽 기둥들중 최대값과 오른쪽 기둥들중 최대값 중에 작은값만 알면 되는거니까.

leftmax가 rightmax보다 작다면 lp를 이동해가면서 계속 갱신하면 되고

아니면 rp를 이동해가면서 계속 계산하면 된다.

알고보니 아직 스캔하지 않은 영역에 엄청 큰 기둥이 있어서 물을 담을 수 있었던걸 계산 못하면 어떡하냐고? 그럴까봐 max값이 작은쪽 포인터를 이동시키는거다. 위 그림에서 max값이 더 큰 오른쪽 포인터를 왼쪽으로 이동하다가 height[8]보다 큰 기둥을 만나면 큰일난다. 하지만 lp부터 이동시키면 i=3에서 leftmax는 확실하게 알고있고 leftmax가 rightmax보다 작다는걸 확실하게 알고있기때문에 오른쪽에 얼마나 큰 기둥이 있든 상관이 없다.

 

public int trap(int[] A){
    int a=0;
    int b=A.length-1;
    int max=0;
    int leftmax=0;
    int rightmax=0;
    while(a<=b){
        leftmax=Math.max(leftmax,A[a]);
        rightmax=Math.max(rightmax,A[b]);
        if(leftmax<rightmax){
            max+=(leftmax-A[a]);       // leftmax is smaller than rightmax, so the (leftmax-A[a]) water can be stored
            a++;
        }
        else{
            max+=(rightmax-A[b]);
            b--;
        }
    }
    return max;
}