[leetcode - 42. Trapping Rain Water] java

문제 설명

1. 블록이랑 높이가 주어진다.

2. 블록 사이에 물이 쌓인다.

3. 물의 총합을 구하면 된다.

풀이 과정 

- 처음에는 백준에 있던 비슷한 문제를 풀었던 경험이 있었어서 그대로 해야지 싶었다.

https://www.acmicpc.net/problem/14719

- 근데 그대로 풀었더니 시간초과가 났다. 그래서 한참 헤맸는데... 투 포인터로 풀면 간단?히?(이미 1시간 넘게 씀) 풀리는 문제였다...

- 뭔가 나는 문제를 보자마자 풀이를 시작하는 버릇을 고쳐야 할 것 같다. 정확히 풀이를 할 수 있다는 확신이 들어야 할듯

1. 투 포인터 + 구현

2. 왼쪽과 오른쪽 끝에서부터 확인해가면서

3. 오른쪽이 더 클 때, 왼쪽의 최대 높이보다 현 왼쪽이 더 큰 경우 최대높이를 갱신해주고, 그렇지 않다면 여기는 물이 쌓인 것으로 계산한다.

4. 왼쪽에서 한칸 포인터 이동

5. 오른쪽도 마찬가지로 해주면 된다.

- 쉽다고 생각하고 풀었는데 풀이방법이 생각나지 않아 너무 오래 걸렸다.

코드

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

        // 각각 투포인터의 시작점
        int left = 0;
        int right = height.length - 1;
        // 오른쪽 / 왼쪽 최대 높이 블록 높이
        int leftMax = 0;
        int rightMax = 0;
        // 물방울 수
        int total = 0;

        while(left <= right) { // 투포인터 시작
            int leftHeight = height[left];
            int rightHeight = height[right];
            if(leftHeight < rightHeight) { // 왼쪽이 더 작은 경우(참고로 이 과정에서 왼쪽 최대가 현재 오른쪽보다 작다는것은 이미 검증된 상태이다.) 
                if(leftMax <= leftHeight) { // 지금이 최대 블록이면 갱신
                    leftMax = leftHeight;
                } else { // 그렇지 않다면 여기는 왼쪽의 최대만큼 물이 쌓인다
                    total += leftMax - leftHeight; 
                }
                left++; // 다음 포인터 진행
            } else { // 요건 오른쪽
                if(rightMax <= rightHeight) {
                    rightMax = rightHeight;
                } else {
                    total += rightMax - rightHeight;
                }
                right--;
            }
        }

        return total;
    }
}