[Grind75-LeetCode] Trapping Rain Water JAVA

반응형

728x90

[Grind75-LeetCode] Trapping Rain Water - Hard

---

접근

• 투 포인터

---

풀이

양의 정수 값으로 배열이 주어지고 정수 값들은 벽(?)의 높이를 나타낸다. 그렇게 만들어진 벽에 비가 올 경우 물이 고이게 되는데 고인 물의 총량을 구하는 문제이다. 저번에 풀었던 컨테이너? 를 만드는 문제와 비슷하다.

2024.11.19 - [알고리즘/코딩테스트-Grind75] - [Grind75-LeetCode] Container With Most Water JAVA

[Grind75-LeetCode] Container With Most Water JAVA

컨테이너의 경우 수직선 두 개를 골라 가장 많은 물을 담을 수 있는 넓이를 구하는 문제이지만 이번 문제는 물이 고일 수 있는 모든 부분을 검사해 비의 총량을 구해야 한다.

 

컨테이너 문제에도 사용했듯이 투 포인터를 통해 풀어진다. 

    public int trap(int[] height) {
        int result = 0;
        
        if (height.length == 0) {
            return result;
        }
        
        int left = 0;
        int leftMax = height[left];

        int right = height.length - 1;
        int rightMax = height[right];

배열이 비어있는 경우 0을 리턴하게 된다. 각 포인터를 초기화하는데 왼쪽 포인터는 왼쪽에서부터 진행하고 오른쪽 포인터는 오른쪽 끝인 배열의 끝에서 진행하게 된다. 비 양 체크를 위해 각 포인터에 해당하는 값들도 따로 변수에 담아준다.

	while (left < right) {
            if (leftMax <= rightMax) {
                left++;
                leftMax = Math.max(leftMax, height[left]);
                result += Math.max(0, leftMax - height[left]);
            } else {
                right--;
                rightMax = Math.max(rightMax, height[right]);
                result += Math.max(0, rightMax - height[right]);
            }
        }

        return result;
    }

두 포인터가 만날 때까지 반복을 수행해 준다. 왼쪽과 오른쪽 벽 중 높이가 낮은 벽을 기준으로 진행하게 되는데 빗물이 고일 때 벽의 낮은 높이를 기준으로 고이기 때문이다. 벽이 1, 0, 2 존재한다면 비가 고일수 있는 가운데 0에는 낮은 벽을 기준으로 1의 높이만큼 고일 수 있기 때문이다. 그렇기 때문에 양쪽 두 벽의 높이를 비교해 낮은 쪽을 기준으로 진행을 해준다. 만약 왼쪽 벽이 낮거나 같을 경우 왼쪽 포인터를 기준으로 진행하게 되는데 여기서 조금 헷갈릴 수 있는 부분이 나온다. 우리는 눈으로 배열을 통해 구성된 벽의 높이를 보고 빗물의 높이를 구할 때 보통 하나의 전체 공간을 보게 된다. 

출처: LeetCode

예제 1번을 시각화한 그림이다. 우리는 눈으로 보고 빗물의 양을 구한다면 아마도 [1:3], [3:7], [8:10] 이렇게 크게 세 부분으로 나누어 빗물의 양을 계산해 더하게 될 것이다. 그런 방법을 코드로 구현하기 위해선 height [1]과 height [3]의 높이를 비교해 빗물의 양을 구하고 height [3]과 height [7] 그리고 height [8]과 height [10]의 높이를 비교하여 구하는 등 비슷한 과정을 수행하게 될 것이다. 그러나 이 방법은 우리가 눈으로 전체적인 구조를 볼 수 있기 때문에 가능한 방법으로 구현을 하기엔 힘든 방법이다. 

	    if (leftMax <= rightMax) {
                left++;
                leftMax = Math.max(leftMax, height[left]);
                result += Math.max(0, leftMax - height[left]);
            }

그렇기 때문에 코드에선 단순히 붙어있는 벽 두개를 비교하여 한 칸씩 빗물이 고일 수 있는지를 체크하고 넘어가게 된다. 왼쪽 벽이 오른쪽 보다 작다고 가정할 때 현재 left인 height [1]과 left를 증가시킨 후 height [2]를 비교하게 된다. 두 값을 비교해 너 높은 벽을 찾고 높은 벽의 높이를 기준으로 현재 벽인 height [2]의 값을 빼주게 되는데 현재 height [1] = 1, height [2] = 0으로 leftMax = 1이 되고 1 - 0을 통해 1이라는 결과가 나오게 된다. 결과 값이 양수라는 뜻은 포인터를 증가시킨 height [2]의 높이가 height [1] 보다 낮아 빗물이 1만큼 고일수 있다는 뜻으로 한 칸씩 빗물의 양을 계산하게 된다. 이 과정을 반복하다 왼쪽 벽이 오른쪽 보다 높아진다면 오른쪽 포인터를 통해 진행하게 되고 두 포인터가 만나게 되면 한 번의 반복으로 모든 계산이 끝났다는 뜻이다. result에서 Math.max를 해주는 이유는 값이 음수로 나온다면 0으로 걸러주기 위해 존재하는 부분이다. 

---

전체 코드

class Solution {
    public int trap(int[] height) {
        int result = 0;
        
        if (height.length == 0) {
            return result;
        }

        int left = 0;
        int leftMax = height[left];

        int right = height.length - 1;
        int rightMax = height[right];

        while (left < right) {
            if (leftMax <= rightMax) {
                left++;
                leftMax = Math.max(leftMax, height[left]);
                result += Math.max(0, leftMax - height[left]);
            } else {
                right--;
                rightMax = Math.max(rightMax, height[right]);
                result += Math.max(0, rightMax - height[right]);
            }
        }

        return result;
    }
}