[C] LeetCode 42. Trapping Rain Water

문제

번역

n개의 음이 아닌 정수 배열이 주어지고, 이 배열은 elevation map(지형 높이 배열, 고도 지도..)로 주어지고, 가로폭은 1이다.

이때, 비가 오고 난 뒤 얼마나 많은 물을 가둘 수 있는지 계산해라.

접근 방법 및 소스 코드

일단 한 칸에 고일 수 있는 물의 양은 

min ( leftMax, rightMax ) - height[i]

이다.

이를 각 칸에서부터 계산하면 \(O(n^2)\) 의 시간복잡도가 나온다.

 

조금 더 효율적인 방법은 없을까? 물론 있다 그러니 문제를 냈겠지

 

양 끝에서 시작하는 l 포인터와 r 포인터가 있다고 하자.

그 포인터는 height 배열의 높이를 가리킨다.

 

두 값중 하나는 상대보다 낮을 것이다. ( 같을 수도 있겠지만 )

아무튼, 낮은 쪽은 반대편에 나보다 높은 벽이 있으니, 그쪽은 걱정 하지 않고 내 쪽의 최대 높이와의 차이만 계산하면 된다.

만약 내가 기존의 최대높이보다 높은 블럭이라면, 물을 담을 수 없으니 최대 높이를 갱신만 하고 끝낸다.

 

이를 코드로 구현하면 다음과 같다.

 

int trap(int* height, int heightSize) {
    int l=0,r=heightSize-1,maxl=height[l],maxr=height[r],map=0;
    while(l<=r) {
        if(height[l] <= height[r]) {
            if(height[l] >= maxl) maxl = height[l];
            else map += maxl-height[l];
            l++;
        } else {
            if(height[r] >= maxr) maxr=height[r];
            else map += maxr-height[r];
            r--;
        }
    }
    return map;
}

 

낮은 쪽만 처리해주면 된다..! 

실행 결과는 다음과 같다.

 

끝!