42. Trapping Rain Water

그림과 같이 빗물을 받을 수 있는 양을 측정하는 문제이다.

 

내가 생각한 방법

1.  가장 높은 벽의 높이를 찾아서 1층부터 가장 높은 층까지 for문을 진행한다.
2. 각 층에서 벽과 벽사이의 빈공간의 개수를 찾는다.

이 방법은 벽의 높이가 커질 수록 무의미하게 계산하는 양이 많아지므로 시간이 오래걸리게 되어 효율적이지 못하다.

 

Two - pointer 방법

1. 왼쪽 포인터와 오른쪽 포인터, 왼쪽 높이 최댓값과 오른쪽 높이 최댓값을 만든다.
2. 만약 왼쪽 포인터 벽 높이와 오른쪽 포인터 벽 높이 중 작은 쪽에서 작업을 수행한다. (왼쪽이라고 가정해보자)
3. 현재 높이가 왼쪽 최대 높이 보다 작을 경우, 최대 높이에서부터 물이 고여있을 것이므로 최대높이-현재높이 만큼 물이 고인다.
4. 만약 현재 높이가 왼쪽 최대높이 보다 클 경우, 현재 높이를 최대 높이로 갱신한다. 

가장 작은 높이의 벽부터 물이 고인다고 생각하며 양쪽에서 좁혀가면, 답을 얻을 수 있다.

 

Two-pointer 많이 해봤는데 조건을 생각하는 것이 많이 어려웠다. 아쉽다.

 

 

나의 소스코드

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) == 0:
            return 0
        ma = max(height)
        result = 0
        for i in range(1,ma+1):
            for j in range(len(height) - 1):
                l = 0
                r = 0
                if height[j] >= i and height[j+1] < i:
                    l = j+1
                    for k in range(j+1,len(height)-1):
                        if height[k] < i and height[k+1] >= i:
                            r = k
                            result += r - l + 1
                            break
        return result

        #밑 줄부터 한줄씩 갇혀있는 부분 계산하는 방법
        #높이가 클 경우 시간이 오래걸려서 시간초과 발생
                        

Two-pointer 소스코드

class Solution:
    def trap(self, height: List[int]) -> int:
        result = 0
        l = 0
        r = len(height) - 1
        max_l = 0
        max_r = 0
        
        while l < r:
            if height[l] < height[r]:
                if height[l] < max_l:
                    result += max_l - height[l]
                else:
                    max_l = height[l]
                l += 1
            else:
                if height[r] < max_r:
                    result += max_r - height[r]
                else:
                    max_r = height[r]
                r -= 1
        return result