[Leetcode] 42번 - 빗물 트래핑

1. 문제 파악

해당 문제 유형은 단순히 구현이나 자료구조와 알고리즘을 아는 것보다 동작을 추상화해서 수식 또는 알고리즘으로 모델링하는 것이 핵심이다.

1. 문제 링크: https://leetcode.com/problems/trapping-rain-water/ (백준: https://www.acmicpc.net/problem/14719)
2. 문제 정의:
   1. 각 인덱스의 요소값은 벽의 높이를 나타낸다.
   2. 양쪽에 벽으로 막혀야 물이 고일수 있으므로, 현재 지정한 벽에서 양쪽 벽의 높이를 알아야한다.
   3. 현재 지정한 벽을 기준으로, 왼쪽에서 가장 높은벽과 오른쪽에서 가장 높은 중에서 작은 쪽과의 차이가 물이 고일수있는 양이다.
3. 문제의 제약 파악 (입력값 크기, 상수 조건)
   • 1 <= nums.length <= 40000: 시간복잡도가 O(NlogN) 이내여야 통과하는데 안전하다.

---

2. 문제 풀이

1. 브루트 포스로 문제 풀이 도출

[0,1,0,2,1,0,1,3,2,1,2,1]에서 각 요소마다 왼쪽 최대값과 오른쪽 최대값을 구해야하므로 O(N^2)이 걸린다.

1. 배열을 순회하면서 물의 양을 계산할 벽을 지정 (인덱스 지정)
2. 왼쪽 벽의 최대크기와 오른쪽 벽의 최대크기를 0으로 초기화
3. 지정한 벽으로부터 배열을 순회하면서 왼쪽 벽의 최대 크기를 업데이트
4. 지정한 벽으로부터 배열을 순회하면서 오른쪽 벽의 최대 크기를 업데이트
5. 물의 양을 구하는 변수에 왼쪽벽과 오른쪽벽 중에서 작은것과 현재 벽의 차이를 더한다.

주의할점은 현재 조회하는 벽이 가장 높은 경우에 차는 물이 0이므로, 최대값을 구할때 현재 탐색하는 벽도 포함시켜야한다.

public int trap(int[] height) {  
    int n = height.length;  
    int water = 0;  
    // 1. 배열을 순회하면서 물의 양을 계산할 벽을 지정 (인덱스 지정)  
    for (int i = 1; i < n - 1; i++) {  
        // 2. 왼쪽 벽의 최대크기와 오른쪽 벽의 최대크기를 0으로 초기화  
        int leftMax = 0;  
        int rightMax = 0;  

        // 주의점: 현재 탐색하는 벽이 제일 높은 경우에 차는 물이 0이므로, 최대값을 구할때 현재 탐색하는 벽도 포함시킨다.  

        // 3. 지정한 벽으로부터 배열을 순회하면서 왼쪽 벽의 최대 크기를 업데이트  
        for (int j = 0; j <= i; j++) {  
            leftMax = Math.max(height[j], leftMax);  
        }  

        // 4. 지정한 벽으로부터 배열을 순회하면서 오른쪽 벽의 최대 크기를 업데이트  
        for (int k = i; k < n; k++) {  
            rightMax = Math.max(height[k], rightMax);  
        }  

        // 5. 물의 양을 구하는 변수에 왼쪽벽과 오른쪽벽 중에서 작은것과 현재 벽의 차이를 더한다.  
        water += Math.min(leftMax, rightMax) - height[i];     
    }  
    return water;  
}

 

2. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?

시간복잡도 내로 풀기 위해서는 O(NlogN)이나 O(N)으로 풀어야한다. 따라서 배열 순회하는 연산빼고 O(logN)이나 O(1)이 걸려야한다.

 

위에서 왼쪽 벽의 최대값을 구하는 로직과 오른쪽 벽의 최대값을 구하는 로직 연산을 O(N)으로 줄일수있는 방법을 생각해보는것이 맞다.

 

그러나 해당 문제는 브루트 포스로 접근하는 것보다 시각적으로 표현되어, 직관적으로 접근하는 것이 더 나은것 같 다. 브루트 포스에서 투포인터를 풀이를 도출하는 것은 어려웠다.

 

직관적으로 문제를 해석한 경로는 다음과 같다.

1. 배열을 순회하는 방향으로 이전까지의 최대값과 현재의 값의 차이가 물의 양이다.
2. 하지만 왼쪽과 오른쪽 방향으로 모두 순회해야 이전까지의 최대값과 현재의 값의 차이가 물의 양을 구할수있다.
3. 따라서 투 포인터를 쓰면 양쪽 방향에서 안쪽으로 순회할수있다. 그러면 포인터가 움직이는 방향으로 이전의 최대값과 현재의 값의 차이가 물의 양이다.
4. 그러나 포인터가 움직여서 도달하는 값이 최대값이어야 이전까지의 최대값과 현재의 값의 차이가 물의 양이 된다. 그러므로 양쪽에서 포인터가 최대값으로 이동하는 뱡향이어야한다.
5. 따라서 투 포인터의 이동 조건은 다음과 같다.
   • 왼쪽 최대값이 오른쪽 최대값보다 같거나 작으면 왼쪽 포인터를 오른쪽으로 이동한다.
   • 오른쪽 최대값이 왼족 최대값보다 작으면 오른쪽 포인터를 왼쪽으로 이동한다. 

     

다음은 위의 문제를 해석함에 따라 풀이한 로직이다.

1. 왼쪽 최대값을 첫번째 요소값으로 초기화한다.
2. 오른쪽 최대값을 마지막 요소값으로 초기화한다.
3. 왼쪽 포인터가 오른쪽 포인터보다 작을 경우 아래의 로직을 반복한다.
4. 왼쪽 최대값이 오른쪽 최대값보다 작거나 같을 경우, 왼쪽 포인터를 오른쪽으로 이동시키고 물의 양에 왼쪽 최대값 - 물의 양에 현재 조회한 값 더한다.
5. 오른쪽 최대값이 왼쪽 최대값보다 작은 경우, 오른쪽 포인터를 왼쪽으로 이동시키고 물의 양에 오른쪽 최대값 - 물의 양에 현재 조회한 값 더한다.
6. 합산된 물의 양을 반환한다.

 

3. 입출력 케이스 도출 및 문제 풀이 도출 확인

• 일반 케이스
  • Example1
    • Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
    • Output: 6
  • Example2
    • Input: height = [4,2,0,3,2,5]
    • Output: 9

위의 핵심 문제풀이에 문제가 될 엣지 케이스는 없다.

 

4. 코드 구현

위의 핵심 문제 풀이 도출에서의 로직으로 코드로 구현하면 다음과 같다. 여기서 주의할점은 현재 조회하는 벽이 이전까지의 벽의 높이와 같거나 높은 경우, 고이는 물이 0이므로 최대값을 구할때 현재 조회하는 벽도 포함시켜야한다. 따라서 현재 조회한 값과 비교해서 왼쪽 오른쪽 최대값을 먼저 구한다.

public int trap(int[] height) {  
    int left = 0;  
    int right = height.length - 1;  
    int leftMax = height[left]; // 1. 왼쪽 최대값을 첫번째 요소값으로 초기화한다.  
    int rightMax = height[right]; // 2. 오른쪽 최대값을 마지막 요소값으로 초기화한다.  
    int water = 0;  
    // 3. 왼쪽 포인터가 오른쪽 포인터보다 작을 경우 반복한다.  
    while (left < right) {  
        // 주의점: 현재 조회하는 벽이 이전까지의 벽의 높이와 같거나 높은 경우, 고이는 물이 0이므로 최대값을 구할때 현재 조회하는 벽도 포함시켜야한다. 따라서 현재 조회한 값과 비교해서 왼쪽 오른쪽 최대값을 먼저 구한다.  
        leftMax = Math.max(height[left], leftMax);  
        rightMax = Math.max(height[right], rightMax);  

        if (leftMax <= rightMax) { // 4. 왼쪽 최대값이 오른쪽 최대값보다 작거나 같을 경우, 왼쪽 포인터를 오른쪽으로 이동시키고 물의 양에 `왼쪽 최대값` - `물의 양에 현재 조회한 값` 더한다.  

            water += leftMax - height[left];  
            left++;  
        } else { // 5. 오른쪽 최대값이 왼쪽 최대값보다 작은 경우, 오른쪽 포인터를 왼쪽으로 이동시키고 물의 양에 `오른쪽 최대값` - `물의 양에 현재 조회한 값` 더한다.  
            water += rightMax - height[right];  
            right--;  
        }  
    }  
    return water; // 6. 합산된 물의 양을 반환한다.  
}

 

5. 복잡도

• 시간 복잡도
  • 배열 순회: O(N)
  • 최종 시간복잡도: 배열 순회 = O(N)