리트코드 - 42. Trapping Rain Water

리트코드 - 42. Trapping Rain Water

출처 - https://leetcode.com/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

각각의 너비가 1인 막대로 표현된 고도 지도를 나타내는 비음수 정수 n개가 주어졌을 때, 비가 내린 후에 저장될 수 있는 물의 양을 계산하십시오.

 

 

의사코드

left = 0 right = height.length - 1 totalWater = 0 leftMax = Integer.MIN_VALUE rightMax = Integer.MIN_VALUE 반복문 시작 (left < right)     leftMax = Math.max(leftMax, height[left])     rightMax = Math.max(rightMax, height[right])     if (leftMax < rightMax)         totalWater += leftMax - height[left]         left++     else         totalWater += rightMax - height[right]         right-- totalWater 리턴

 

풀이코드

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int totalWater = 0;
        int leftMax = Integer.MIN_VALUE;
        int rightMax = Integer.MIN_VALUE;

        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            if (leftMax < rightMax) {
                totalWater += leftMax - height[left++];
            } else {
                totalWater += rightMax - height[right--];
            }
        }

        return totalWater;
    }
}

코드설명

배열로 블럭이 주어질 때 가둘 수 있는 물의 양을 구하는 문제이다.

빗물이 가두어지는 조건은 왼쪽의 높이와 오른쪽의 높이가 같아야 한다.

저장되는 빗물을 구하는 방법은 이 높이에서 왼쪽과 오른쪽 사이에 있는 값들을 빼주면 된다.

둘의 높이가 다르면 어떻게 할까?

둘의 높이가 다르다면 낮은 값을 기준으로 계산하게 된다.

일단 이렇게 웅덩이가 하나인 경우는 생각보다 간단해보인다.

만약 웅덩이가 2개라면 어떻게 할까?

높을 쪽을 기준으로 하나씩 더해주면 된다.

 

가운데가 높을 때도 마찬가지이다.

그러면 이제 높은 값을 어떻게 만들어줄 것인가가 핵심이 된다.

 

정답은...갱신하면 된다 이다. 투포인터를 사용하는게 효율적으로 보인다.

처음에 left에는 2가 저장되고, right에는 3이 저장된다.

둘을 비교하여 3이 높으므로 3을 향해 left가 한칸씩 이동해야 한다.

 

이렇게 이동하다가 left가 4가 되면 left가 right보다 높아지므로 이번에는 right이 이동하기 시작한다.

최종적으로 left와 right가 만나면 모든 계산이 완료된다.

 

코드에서 leftMax와 rightMax는 양 포인터의 최대 높이를 저장하는 변수이고, if문 내에서 높이 값을 비교하고 있다.

totalWater 에서는 물의 양을 더하고 있는데, 포인터를 이동할 때 해당 기둥의 Max값을 빼주면 기둥에서는 0만큼만 더할 수 있다.

최대 높이가 갱신되지 않는 이상 계속 Max값을 빼게 되면 같힌 물의 양을 구할 수있다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

정리

투포인터를 이용하여 물의 높이를 계산하는 방법