[Leetcode 42] Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/description/

 

1. 문제설명

• 각 높이를 나타내는 지도가 주어졌을 때, 얼만큼 물이 담길 수 있는지 계산

 

2. 문제해결

[stack 이용]

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        water = height.copy()

        for i, h in enumerate(height):
            if stack and stack[-1][1] <= h:
                while stack and stack[-1][1] <= h:
                    cur_i, cur_h = stack.pop()
                if stack:
                    cur_i = stack[-1][0]
                    for j in range(cur_i+1, i):
                        water[j] = h
                else:
                    for j in range(cur_i, i):
                        water[j] = cur_h
            stack.append([i, h])

        result = 0
        for i in range(len(water)):
            result += (water[i]-height[i])
        return result

• 현재 높이랑 마지막에 저장된 높이랑 비교하는 과정이 필요하므로 stack 이용
  • stack이 들어 있고 현재 높이가 stack의 맨 끝 높이보다 크거나 같으면 pop 반복
• pop 후에 stack 확인
  • stack이 비어 있으면 현재 높이보다 모두 작은 높이이므로 마지막에 pop된 높이로 모두 저장 (stack의 맨 앞 요소는 stack의 담긴 높이들 중 가장 높음)
  • stack이 남아 있으면 현재 높이보다 더 큰 높이가 있으므로 현재 높이로 물 채우기
• 어디서부터 어디까지 채울지 범위 잘 생각하기
• 마지막에 벽의 높이 - 저장된 높이로 갱신

 

[투 포인터 이용]

class Solution:
    def trap(self, height: List[int]) -> int:
        left_max = height[0]
        right_max = height[-1]
        l = 0
        r = len(height)-1
        water = height.copy()

        while l <= r:
            if left_max <= right_max:
                if height[l] <= left_max:
                    water[l] = left_max
                else:
                    left_max = height[l]
                l += 1 
            else:
                if height[r] <= right_max:
                    water[r] = right_max
                else:
                    right_max = height[r]
                r -= 1
        
        result = 0
        for i in range(len(water)):
            result += (water[i] - height[i])
        return result

"물이 담기려면 양쪽 벽이 세워져 있어야 한다."

• 첫번째 벽 확인
  • 왼쪽 최대 높이와 오른쪽 최대 높이를 비교하면서 작은 쪽의 인덱스를 한 칸씩 움직인다.
• 두번째 벽 확인
  • 작은 쪽의 현재 높이가 작은 쪽의 최대 높이보다 작으면 물 채우기 (크면 최대 높이 갱신)

ex) 만약 오른쪽의 최대 높이가 왼쪽의 최대 높이보다 더 높으면, 오른쪽 벽에 의해 물이 담길 수 있다. 그리고 왼쪽에도 벽을 세워야 마침내 물을 담을 수 있으므로, 왼쪽 최대 높이와 왼쪽 인덱스에 대해 현재 높이를 비교한다. 최대 높이보다 현재 높이가 더 작아야 물이 담길 수 있으므로 이를 비교한다.