[LeetCode] Trapping Rain Water (Java)

문제

문제풀이 1. 두 번 계산해주자

- DP로 풀었다.
- 두 가지 경우를 나누어 앞에서 부터 탐색했을 때와 뒤에서부터 탐색했을 때를 모두 계산해줬다.
  처음에 기준 높이를 가지고 앞에서 부터 탐색할 때 기준 높이보다 높거나 같은 막대를 만나지 못하면 계산이 안된다.
  따라서 뒤에서 부터도 똑같은 방식으로 탐색을 해주고,
  DP배열을 한 번 더 돌아서 각 위치에서 더 낮은 값을 결과값으로 더해줬다.

class Solution {
    public int trap(int[] height) {
        int currHeight = height[0];
        int[][] dp = new int[2][height.length];
        dp[0][0] = 0;
        dp[1][height.length - 1] = 0;

        for (int i = 1; i < height.length; i++) {
            if (height[i] >= currHeight) {
                dp[0][i] = 0;
                currHeight = height[i];
            } else {
                dp[0][i] = currHeight - height[i];
            }
        }

        currHeight = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            if (height[i] >= currHeight) {
                dp[1][i] = 0;
                currHeight =height[i];
            } else {
                dp[1][i] = currHeight - height[i];
            }
        }

        int result = 0;

        for (int i = 0; i < height.length; i++) {
            result += Math.min(dp[0][i], dp[1][i]);
        }

        return result;
    }

}

- 사실 풀면서, 이걸 꼭 두 번 돌아야 하나? 한 번 반복문으로 끝낼 수는 없나? 라고 생각했는데,
  멋진 풀이가 있어 참고하여 다시 풀어보았다.

문제풀이2. 투 포인터를 이용해 한 번의 반복문으로 끝내자

- 먼저, 주어진 벽의 맨 끝에 포인터를 두고 생각해보자.
- 왼쪽이 오른쪽보다 벽의 높이가 더 낮다면, 우리는 왼쪽부터 탐색을 시작할 것이다.
  반대로 오른쪽이 왼쪽보다 벽의 높이가 더 낮다면, 오른쪽부터 탐색을 시작해야 물이 얼마나 고였는지를 탐색할 수 있다.

  이런 원리를 통해 왼쪽과 오른쪽에 포인터를 두고, 더 낮은 쪽부터 옆 방향으로 탐색을 진행해주는 것이다.

- 각 포인터가 만나기 전까지만 탐색을 진행해주고, 왼쪽과 오른쪽에서 가장 높은 길이는 얼마인지는 계속 탐색해주면서 진행해준다.
  왼쪽/오른쪽 높이의 최대값이 더 낮은 애부터 탐색을 하면서 결과값에 값을 더해준다.

class Solution {
    public int trap(int[] height) {
        
        int leftIdx = 0, rightIdx= height.length - 1; // 각 포인터의 인덱스
        int leftMax = Integer.MIN_VALUE, rightMax = Integer.MIN_VALUE; // 각 파트의 최대 높이
        int result = 0; // 결과값 저장

        while (leftIdx < rightIdx) {
            leftMax = Math.max(leftMax, height[leftIdx]); // 각 파트의 최대 높이 갱신
            rightMax = Math.max(rightMax, height[rightIdx]);
            // 낮은 쪽 먼저 탐색하여 결과값에 저장해줌
            result += (leftMax < rightMax) ? leftMax - height[leftIdx++] : rightMax - height[rightIdx--];
        }

        return result;

    }

}

 

- 결과는 비슷하다. 문제의 데이터 범위가 굉장히 작기도 해서  iterator가 1번이냐 3번이냐로는 많은 성능 차이가 발생하지 않는 것 같다.