[Algorithm][LeetCode][Hard][Python] 42. Trapping Rain Water

거의 한 달만에 포스팅하는 알고리즘 코딩 글이다.

 

바빴기도 하지만, 나태해진 이유도 있는 것 같다.

 

 

이 문제는 Solution이 있는 문젠데, 

 

개인적으로 좋은 문제라고 생각되어서

 

Solution에 있는 풀이 중 한 방법에 대해 작성해봤다.

 

 

문제는 여기에서 볼 수 있다.

 

---

 

문제

문제 설명에 나오는 그림만 봐도 어떤 문제인지 알 수 있다.

 

출처) https://leetcode.com/problems/trapping-rain-water/

 

N개의 기둥들의 높이가 담긴 배열이 주어질 때,

 

하늘에서 비가 내린다고 가정하면

 

얼마나 많은 양의 물이 기둥들 사이에 갇히는 지에 대한 문제이다.

 

 

풀이

사실 이 문제도 두 번째 풀어보는 것인데,

 

두 번의 풀이 모두 Brute Force로 해결하려 했었다.

 

 

하지만, Solution만 봐도 Dynamic Programming(DP)나

 

Stack을 이용한 풀이 등 다양한 풀이가 존재한다.

 

 

그러나 역시 이러한 배열과 관련된 문제에서는

 

Two Pointers 방법이 가장 좋은 것 같다.

 

 

투 포인터 알고리즘에 대한 설명은 넘어가고,

 

이 문제에서 투 포인터를 적용하기 위해서는

 

좌, 우 인덱스를 나타내는 변수 뿐만 아니라(left, right)

 

좌, 우 기둥의 MAX 높이 값을 저장할 변수들(left_max, right_max)이 필요하다.

 

 

아래는 내가 작성한 풀이다.

 

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        left_max, right_max = 0, 0
        left, right = 0, len(height) - 1
        
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    ans += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    ans += right_max - height[right]
                right -= 1
        return ans

 

아래는 위 풀이의 퍼포먼스이다.

 

퍼포먼스

 

사실 나도 깜짝 놀랐다.

 

100% 빠른 풀이는 처음 봤는데,

 

'역시 투 포인터다...' 생각이 든다.

 

---

 

곧 상반기 채용 철이 다가온다.

 

 

나태해지지 말고,

 

열심히 준비하자.

 

 

끝!