[리트코드 42] 투 포인터(Two Pointers) 를 활용한 문제풀이2

*투 포인터에 대해 모른다면 [리트코드 334] 투 포인터(Two Pointers) 를 활용한 문제풀이1 참고.

 

난이도가 높은 문제로 여러 가지 방법으로 풀 수 있지만 투 포인터를 이용하면 가장 높은 막대에서 좌우 포인터가 만나므로 시간복잡도 O(n) 로 풀이가 가능하다. (python, kotlin 두 언어로 풀이)

42. 빗물 트래핑

Example

- 각 막대의 너비가 1인 고도를 나타내는 음이 아닌 정수 n개가 주어지면 비가 내린 후 얼마나 많은 물을 가둘 수 있는지를 계산한다.

Constraints

- n은 height의 길이이다.

- 1 <= n <= 2 * 10^4

- 0 <= height[i] < 10^5

Solution

- 포인터를 양쪽 끝에 위치시킨 뒤, 막대의 높이가 최대인 지점에서 포인터가 만날때 까지 루프를 돌며, 좌우 막대의 최대 높이와 현재 높이의 차이 만큼 빗물의 양을 더해준다.

Step

과정이 복잡하므로 이해를 높이기 위해 while 문에 과정을 나열해보면 다음과 같다.

 

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

l = 0, r = 11 일때 water = 0

l_max = height[0] = 0

r_max = height[11] = 1

왼쪽 막대 높이가 작으므로 현재 높이와 왼쪽 막대 높이 차이만큼 물의 양을 더 한 후,

왼쪽 포인터가 오른쪽으로 +1 이동한다.

 

l = 1, r = 11 일때 water = 0

l_max = height[1] = 1

r_max = 1

좌우 높이가 같으므로 현재 높이와 왼쪽 막대 높이 차이만큼 물의 양을 더 한 후,

왼쪽 포인터가 오른쪽으로 +1 이동한다.

 

l = 2, r = 11 일때 water = 0

l_max = max(height[2], 1) = 1

r_max = 1

좌우 높이가 같으므로 현재 높이와 왼쪽 막대 높이 차이(1-0 = 1)만큼 물의 양을 더 한 후,

왼쪽 포인터가 오른쪽으로 +1 이동한다.

 

l = 3, r = 11 일때 water = 1

l_max = max(height[3], 1) = 2

r_max = 1

오른쪽 막대 높이가 작으므로 현재 높이와 오른쪽 막대 높이 차이(1-1 = 0)만큼 물의 양을 더 한후,

오른쪽 포인터가 왼쪽으로 -1 이동한다.

 

l = 3, r = 10 일때 water = 1

l_max = 2

r_max = max(height[10], 1) = 2

좌우 높이가 같으므로 현재 높이와 왼쪽 막대 높이 차이(2-2 = 0)만큼 물의 양을 더 한 후,

왼쪽 포인터가 오른쪽으로 +1 이동한다.

 

l = 4, r= 10 일때 water = 1

l_max = max(height[4], 2) = 2

r_max = 2

좌우 높이가 같으므로 현재 높이와 왼쪽 막대 높이 차이(2-1 = 1)만큼 물의 양을 더 한 후,

왼쪽 포인터가 오른쪽으로 +1 이동한다.

 

l = 5, r = 10 일때 water = 2

l_max = max(height[5], 2) = 2

r_max = 2

좌우 높이가 같으므로 현재 높이와 왼쪽 막대 높이 차이(2-0 = 2)만큼 물의 양을 더 한 후,

왼쪽 포인터가 오른쪽으로 +1 이동한다.

...

 

-> 최대 막대 높이에서 두 포인터가 만날때까지 위의 과정을 반복하며 빗물의 양을 더해준다.

코드 샘플

# python
class Solution:
    def trap(self, height: List[int]) -> int:
        water = 0  # 빗물의 양
        
        # 양쪽 끝에 포인터를 위치 시킨다.
        l, r = 0, len(height) - 1
        
        l_max = height[l]  # 왼쪽 막대 최대 높이
        r_max = height[r]  # 오른쪽 막대 최대 높이
        
        
        # 투 포인터가 서로 겹치지 않을때까지 loop
        while l < r:
            l_max = max(height[l], l_max)
            r_max = max(height[r], r_max)
            
            # 최대 높이에서 만나야함으로 왼쪽 막대 높이가 낮은 경우 오른쪽으로 한칸 이동한다.
            if l_max <= r_max:
                # 왼쪽 막대 최대 높이와 현재 높이의 차이 값 만큼 물의 양을 더해준다.
                water += l_max - height[l]
                l += 1  
            else:
                water += r_max - height[r]
                r -= 1
        return water

 

# kotlin
class Solution {
    fun trap(height: IntArray): Int {
        var water = 0

        var l = 0
        var r = height.size - 1
        var lMax = height[l]
        var rMax = height[r]

        while(l < r) {
            lMax = maxOf(height[l], lMax)
            rMax = maxOf(height[r], rMax)

            if (lMax <= rMax) {
                water += lMax - height[l]
                l++
            } else {
                water += rMax - height[r]
                r--
            }
        }
        return water
    }
}

실행 결과

 

참조: 파이썬 알고리즘 인터뷰 https://github.com/onlybooks/algorithm-interview