[Leetcode] 42. Trapping Rain Water

문제

위 처럼 높이가 들어있는 배열 height이 주어졌을 때
각 너비가 1인 막대기들 사이에서 물이 얼마나 가두어졌는지 계산하라

접근

처음에 DP로 풀기위해서 배열의 처음부터 끝까지 한 번만 순회하는
로직을 생각하고 있었는데, 생각보다 로직이 잘 떠오르지 안아서
계속 고민하다가 결국 힌트를 보았다.

Two Pointer로 풀 수 있다는 힌트가 있어서 양 끝을 가르키는
변수 두 개를 두고 해야하는 문제인가..? 싶었는데 정답이었다.

Two Pointer라는 힌트를 얻고도 꽤나 오래 고민했는데
나는 직관적으로 단번에 떠오르지 않으면 풀기 어렵다고 느꼈다.

접근방식을 살펴보자.

내가 그림을 명확하게 그리지 못해서 헷갈릴 수 있다..

처음에 Left_Max와 Right_Max를 각각의 배열 처음과 끝으로 설정해두자.
위의 그림대로면 0과 1로 각각 초기화 될 것이다.
인덱스를 지정할 변수 역시 i = 1, j = (last_index) 로 지정해주자.

순회하면서 현재 height[i] > Left_Max라면
Left_Max = height[i]로 새롭게 갱신해준다.

그 다음

• Left_Max <= Right_Max 라면 ans += Left_max - height[i]
• Left_Max > Right_Max 라면 ans += Right_max - height[j]

이 부분이 잘 떠오르지 않아서 문제였다.

직접 그린거라 허졉해보이지만
Left_Max와 Right_Max가 위의 사진 처럼 3과 4로 되어 있을 때
더 높은 기둥이 나오기 전 까진 Left_Max 와 Right_Max 둘 중
작은 기둥의 높이를 기준으로 "반드시 모든 기둥 사이는 물이 채워진다"




물의 높이는 현재 i 인덱스의 기둥높이 즉 height[i] 와
Right_Max보다 낮은 기둥 Left_Max 을 이용하여 구할 수 있다.

물의 높이 = Left_Max - height[i]

따라서 다음과 같이 코드가 짜여진다.

def trap(self, height: List[int]) -> int:
        
        left_max = height[0]
        right_max = height[-1]
        ans = 0
        i = 1
        j = len(height) - 1

        if j <= 1:
            return 0
        
        while i <= j:
            if height[i] > left_max: left_max = height[i]
            if height[j] > right_max: right_max = height[j]

            if left_max <= right_max:
                ans += left_max - height[i]
                i += 1
            else:
                ans += right_max - height[j]
                j -= 1
        return ans

조금 어렵게 생각했는데 생각보다 쉬웠고
개인적으로는 접근하는게 좀 힘들었다!