LeetCode 42 Trapping Rain Water Hard [Java]

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

Trapping Rain Water - LeetCode

1. 코드

class Solution {
    public int trap(int[] height) {
        int answer = 0;
        Pointer.height = height;
        Pointer left = new Pointer(0);
        Pointer right = new Pointer(height.length - 1);

        while(left.index < right.index) {
            left.maxCheck();
            right.maxCheck();

            if(left.max <= right.max) {
                answer += left.max - left.value();
                left.moveToRight();
            }
            else {
                answer += right.max - right.value();
                right.moveToLeft();
            }
        }
        return answer;
    }
}

class Pointer {
    static int[] height;
    int index;
    int max;

    Pointer(int index) {
        this.index = index;
    }

    void maxCheck() {
        max = Math.max(height[index], max);
    }

    void moveToRight() {
        index++;
    }

    void moveToLeft() {
        index--;
    }

    int value() {
        return height[index];
    }
}

2. 설명

왼쪽과 오른쪽을 기준으로 높은 장벽으로 둘러싸인 부분의 부피를 구하는 문제인데 투 포인터를 이용하여 쉽게 해결할 수 있다. 각 포인터의 최대 값을 구하고 왼쪽의 포인터가 오른쪽 포인터의 최댓값이 작거나 같다면 왼쪽 포인터의 위치에서 최댓값을 뺀 값을 answer에 더한 뒤 오른쪽으로 이동시킨다. 아니면 오른쪽 포인터의 현재 값과 최댓값을 뺀 값을 answer에 더한 뒤 왼쪽으로 이동시키다. 그리고 이것을 투 포인터가 겹칠 때까지 반복한 뒤 종료되면 answer를 출력하면 된다.

3. 정리

해당 문제에 대해서 원활하게 해결하지 못하여 투 포인터를 이용한 해결방안을 보았는데 해당 내용도 이해가 되지 않아서 포인터 객체를 만들어서 다시 코드를 작성하니 그나마 이해가 된 것 같다.