LeetCode #42 Trapping Rain Water

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #42 Trapping Rain Water

문제 풀이

투포인터와 스택으로 풀이할 수 있다. 투포인터는 왼쪽과 오른쪽에서 출발하며 왼쪽과 오른쪽 사이의 높이 변화가 어찌 되었건 양쪽 높이 중 더 작은 쪽보다 낮은 지점이 있다면 물의 양이 보장된다는 개념에서 출발한다. 그리고 포인터의 이동 기준은 앞에서 말한대로 물의 양이 낮은 쪽 높이를 기준으로 결정되므로 낮은 값의 포인터를 이동시킨다. 그러다보면 가장 높은 값을 가진 포인터의 위치가 고정되고 한 개의 포인터가 마저 이동하면서 물의 양을 계산한다.

스택을 이용한 풀이는 직관적이나 코드로 작성하기에는 조금 더 난이도가 있다. 0에서 출발해 매번 스택에 값을 넣으면서 변곡점이 있는지 체크한다. 그리고 변곡점이 발생한 지점이 감지되면 이전까지 높이가 계속 낮아지거나 같았음을 의미하므로 스택에서 하나씩 꺼내 높이 차이와 거리를 곱해 물의 양을 계산한다.

python 코드 - 1

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

python 코드 - 2

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        vol = 0
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                distance = i - stack[-1] - 1
                water = min(height[i], height[stack[-1]])
                vol += water * distance
            stack.append(i)
        return vol