[Leetcode 42] Trapping Rain Water - 투 포인터

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

Trapping Rain Water - LeetCode

 

Problem

높이를 입력 받아 얼마나 많은 물이 쌓일 수 있는 지 계산

 

입력 : [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

출력 : 6

 

전략

 

0번 인덱스과 1번 인덱스는 물을 넣어도 왼쪽 경계가 없기 때문에 옆으로 쏟아진다. 하지만 2번 인덱스는 정확히 한 블록의 물을 가둘 수 있다.  만약 2번 인덱스에 하나의 물을 더 채운다면 오른쪽 경계가 있어 괜찮지만 왼쪽은 높이가 모잘라 왼쪽으로 쏟아진다. 즉, 물의 높이는 왼쪽 경계와 오른쪽 경계 중 최솟값이 높이로 선택되게 된다. 각 인덱스마다 정확히 얼마나 많은 물을 가둘 수 있는 지 결정을 할 수가 있다. 먼저 각 위치(인덱스)에서 왼쪽에 최대 높이(L)가 필요하고, 오른쪽에 최대 높이(R)이 필요하고 이 둘 중에 최소값을 가져와야 한다.

 

예를들어, 3번 인덱스를 보면 최대 왼쪽 높이 1 , 최대 오른쪽 높이는 3 이므로 이 둘의 최소값 min(L,R) = 1 이다. 그런데 3번인덱스의 높이는 2 이므로 0의 물의 높이를 가진다. i번째 인덱스의 높이를  h[i]로 두면 다음과 같이 식을 만들 수 있다. 

MIN(L,R) - h[i]

 

다시 위 예제를 계산식에 대입하면 1 - 2 는 음수이지만 높이는 정수이므로 0 으로 결과가 도출된다. 다음 인덱스로 이동하여 4번 인덱스를 보자. 위 계산식에 대입하면 MIN(2,3) - 1 = 1 이 나온다. 이 위치에 정확히 하나의 물을 가둘 수 있다는 의미이다. 모든 위치에서 위와 같은 계산을 하고 더하면 6의 결과를 얻게 된다. 

 

만약 이 문제를 단순히 하나의 인덱스마다 최대 왼쪽, 최대 오른쪽을 찾고 높이를 찾는 방식은 O(n²) 에 풀이가 가능하다. 

더 효율적인 방식으로 다음과 같이 풀도록 한다.

 

투 포인터를 이용

 

 

계속 이런 방식으로 좌우 어느쪽이든 낮은 쪽은 높은 쪽을 향해서 포인터가 가운데로 점점 이동한다. 진행하며 물의 크기를 누적 시키면 시간복잡도 O(n)에 풀이가 가능하다. 전체 코드는 다음과 같다.

 

public int trap(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int waterValue = 0;

    int maxL = height[left];
    int maxR = height[right];

    while (left < right) {
    
        maxL = Math.max(height[left], maxL);
        maxR = Math.max(height[right], maxR);
        
        if (maxL <= maxR) {
            waterValue += maxL - height[left];
            left += 1;
        } else {
            waterValue += maxR - height[right];
            right -= 1;
        }
    }

    return waterValue;

}