LeetCode: 42번 (Trapping Rain Water) [JAVA]

문제 링크

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

Trapping Rain Water - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 현 위치에서 접하게 되는 왼쪽과 오른쪽의 가장 긴 벽을 표시하기 위한 2개의 배열 생성
2. 왼쪽 벽을 표시하기 위한 배열의 경우 배열의 시작부터 끝으로 가면서 동일 배열의 이전 값과 height 배열의 현 위치값 중 더 큰 값을 비교해 저장
3. 반대로 오른쪽 벽을 표시하기 위한 배열의 경우 배열의 끝부터 시작으로 가면서 동일 배열의 이후 값과 height 배열의 현 위치값 중 더 큰 값을 비교해 저장
4. 최종적으로 물의 양을 계산하고자 배열을 돌며 현재의 위치에서 자신의 왼쪽과 오른쪽 중 짧은 벽을 찾아 현 위치와 차이만큼을 물의 양으로 계산

 문제 자체의 난이도는 hard지만, 나름의 아이디어를 떠올리면 쉽게 문제를 해결할 수 있다. 문제에서 요구하는 부분은 주어진 height 배열 중 일종의 틈이 생기는 부분의 총합을 구해 반환하면 된다. 결국 현재 위치에서 틈이 얼만큼인지를 구하기 위해선, 현재 위치에서 왼쪽, 오른쪽에 대해 접하게 되는 가장 긴 벽(큰 높이)의 값들을 각각 알아야 하고, 해당 벽들 중 더 작은 값과 현 위치의 차이가 틈이 된다.
 그렇기 때문에 2개의 벽 길이를 따로 저장하기 위해 2개의 배열을 생성하고, 두 배열에 대해 다른 방향으로 벽의 길이를 계산해준다. 하나는 왼쪽에서 오른쪽(배열의 시작에서 끝)으로 가며 이전 값들 중 현재 위치가 접하는 가장 긴 벽을, 다른 하나는 오른쪽에서 왼쪽(배열의 끝에서 시작)으로 가며 앞선 값들 중 현재 위치가 접하는 가장 긴 벽을 저장해준다. 이후에는 전체 배열을 돌며 현재 위치에서 자신의 왼쪽과 오른쪽 중 짧은 벽을 찾고, 해당 높이와 현재 위치의 차이만큼을 빼 물의 양으로 추가한 다음 해당 값을 반환한다.

 

class Solution {
    public int trap(int[] height) {
        int waterAmount = 0;
        int[] leftToRight = new int[height.length], rightToLeft = new int[height.length];
        leftToRight[0] = height[0];
        rightToLeft[height.length - 1] = height[height.length - 1];

        //왼쪽에서 오른쪽으로 가며 현재 구간이 접하는 가장 긴 벽을 표시
        for (int i = 1; i < height.length; i++) {
            leftToRight[i] = Math.max(height[i], leftToRight[i - 1]);
        }

        //오른쪽에서 왼쪽으로 가며 현재 구간이 접하는 가장 긴 벽을 표시
        for (int i = height.length - 2; i >= 0; i--) {
            rightToLeft[i] = Math.max(height[i], rightToLeft[i + 1]);
        }

        //현재의 위치에서 자신의 왼쪽과 오른쪽 중 짧은 벽을 찾아 현 위치와 차이만큼을 물의 양으로 계산
        for (int i = 0; i < height.length; i++) {
            waterAmount += Math.min(leftToRight[i], rightToLeft[i]) - height[i];
        }

        return waterAmount;
    }
}

결과