42. Trapping Rain Water

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

Trapping Rain Water - LeetCode

난이도 : hard

문제

높이를 입력받아 비 온 후 얼마나 많은 물이 샇일 수 있는지 계산 하라.

 

빗물이 고여있는 파란색 부분의 총합을 계산하는 문제이다.

 

문제의 제약사항은 아래와 같다.

• n == height.length
• 1 <= n <= 2 * 10^4

n 은 최대 10 ^ 4 * 2 에 정수가 입력으로 온다. bruth-foces(이중 반복문) 로 풀이 time-limited 가 발생 할 수 있음으로 O(N) 으로 해결 할 수 있는 방안을 생각 해야 한다. 

처음 생각한 풀이 방식은

왼쪽에서 오른쪽으로 큰수를 채우고, 오른쪽에서 큰수를 채워서 양쪽 값에 최소 값을 height에서 빼는 식으로 생각을하고 코드를 풀었다.

left -> right 로 가면서 현재 면적을 인접한 가장 큰 높이로 채운다.

right -> left 로 가면서 모든 면적을 인접한 가장큰 높이로 채운다.

left, right 배열을 최소값을 구한다. 각각의 요소의 최소값은 아래와 같게 된다. 해당 부분이 빗물이 고이는 영역이며 총합을 반환 하면 문제를 풀 수 있다.

 

코드

시간복잡도는 총 height.size() 만큼 반복하며 1중 반복문을 3개 사용하였음으로 O(3N) -> O(N) 이 시간복잡도를 갖는다.

공간복잡도 또한 height.size 만큼 2개의 동적 배열을 사용하였음으로 O(2N) 의 복잡도를 갖는다.

class Solution {
public:
    int trap(vector<int>& height) {
        int fCnt = height.size();
        vector<int> left(fCnt, 0);
        vector<int> right(fCnt, 0);
        
        int prevValue = height[0];
        for(int i = 0; i < fCnt; ++i) {
            prevValue = max(prevValue, height[i]);
            left[i] = prevValue;
        }
        
        prevValue = height[fCnt - 1];
        for(int i = fCnt - 1; i >= 0; --i) {
            prevValue = max(prevValue, height[i]);
            right[i] = prevValue;
        }
        
        int sol = 0;
        for(int i = 0; i < fCnt; ++i) {
            sol += min(left[i], right[i]) - height[i];
        }
        
        return sol;
    }
};

 

Two-Pointer 사용

시간 복잡도 O(N)

    int trap(vector<int>& height) {

        int left = 0;
        int right = height.size() - 1;
        
        int sol = 0;
        int leftMax = height[left];
        int rightMax = height[right];
        while(left <= right) {
            leftMax = max(height[left], leftMax);
            rightMax = max(height[right], rightMax);
            
            // 더 높은 쪽을 향해 투 포인터 이동
            if( leftMax <= rightMax) {
                sol += leftMax - height[left];
                left++;
            }
            else {
                sol += rightMax - height[right];
                right--;
            }
        }
        
        return sol;
    }