42. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/description/?envType=featured-list&envId=top-google-questions

input :

• height

output :

• 비가 오고 난 후 고여 있을 수 있는 물의 양을 출력하시오.

조건 :

• 검은 색으로 표현된 건물들 사이에 파란 색으로 물을 표현한 것이니 이를 보고 문제를 해결하시오.

---

Solution explain : Solution1

idea

• 3번의 반복문을 통해서 구하는 방법이 있다.
• 처음 모든 원소를 순회하며 현재까지 가장 높은 건물의 높이로 초기화를 한다.
• 반대쪽에서부터 오면서 현재까지 제일 높은 건물의 높이로 다시 초기화를 한다. (이렇게 하면 도중에 height[i], temp_height[i]가 동일해지는데 거기부턴 초기화를 할 필요가 없다.)
• 이렇게 하면 temp_height에 비가 와서 고여있는 값들까지 다 포함하여 만들어진다.
• 해당 값을 구하기 위해 (temp_height[i] - height[i])를 수행하면서 이 값을 ret에 저장한다.

• 투 포인터 방식을 통해 해결하자.
• 물 고인 것을 판단하기 위해서는 현재 기준으로 maxLeft, maxRight 중 작은 값에다가 height[i]를 계산하는 것이다.

---

• 현재 [2, 1, 3, 1, 4]와 같이 오른쪽으로만 커지는 건물들이라면 left, right = 0, len(height) - 1로 초기화를 하면 right는 고정되어 있을 것이다.
• 현재 left, right를 가지고 비교를 하면 left 포인터가 가리키는 것이 오른쪽 보다는 작음을 알 수 있다.
• 그러면 이 값을 maxLeft와 비교해서 그 차를 가져 가면 된다.
• 만약 [2, 1, 3, 1, 2]라면? 이는 [2, 1, 3], [3, 1, 2]로 구분해서 이를 볼 수 있다. 결국 height[left] > height[right]의 경우라면 왼쪽으로 커지는 건물들 즉 2번째 경우이고 반대라면 오른쪽으로 커지는 건물들 인것이다.

• height[left] > height[right]을 통해 현재 위치가 왼쪽으로 커지는 건물들, 오른쪽으로 커지는 건물들 중 무엇인지 확인한다.
• val_위치 > max_위치를 통해서 현재 위치에 새롭게 높은 건물이 나왔는지 확인한다.
• 새로운 건물이 아니면 비가 고였을 것이고, 그렇지 않으면 업데이트 한다.
• 그리고 위치를 늘리거나 줄인다.

• 마지막 의문은 height[left] > height[right]일 떄, maxRight, height[left]의 값에서 꼭 maxRight가 작은 것이 맞는가인데
• 이에 대한 가설은 right를 줄이게 만들어도 left는 움직이지 않고 고정된다. 결국에 변동이 있는 것은 maxRight일 뿐이고 계속 그거보다 left는 크니까 그렇지 않을까 싶다.
• 물론 정확하진 않은데 코드 2개 다 만들었을때 잘 돌아가긴 하더라.

주의

class Solution:
    def trap(self, height: List[int]) -> int:
        length = len(height)
        temp_height = [0] * length

        prev_max = 0
        for i in range(length):
            prev_max = max(prev_max, height[i])
            temp_height[i] = prev_max

        prev_max = 0
        for i in range(length - 1, -1, -1):
            if temp_height[i] == height[i]:
                break
            prev_max = max(prev_max, height[i])
            temp_height[i] = prev_max

        ret = 0
        for i in range(length):
            ret += (temp_height[i] - height[i])

        return ret

# class Solution:
#     def trap(self, height: List[int]) -> int:
#         ret = 0
#         left, right = 0, len(height) - 1
#         max_left, max_right = 0, 0
#
#         while left < right:
#             val_left, val_right = height[left], height[right]
#             if val_left > val_right:
#                 if max_right < val_right:
#                     # 새로운 가장 높은 지점을 찾은 경우
#                     # 물이 채워지지 않고 값만 업데이트
#                     max_right = val_right
#                 else:
#                     # 현재 지점은 다른 두 높은 건물에 쌓여있음
#                     # 이 떄 왼쪽은 아까 포인터가 가리킨 벽이 있고
#                     # 오른쪽은 maxRight가 있음.
#                     ret += (max_right - val_right)
#                 right -= 1
#             else:
#                 if max_left < val_left:
#                     max_left = val_left
#                 else:
#                     ret += (max_left - val_left)
#                 left += 1
#         return ret

# class Solution:
#     def trap(self, height: List[int]) -> int:
#         ret = 0
#         left, right = 0, len(height) - 1
#         max_left, max_right = 0, 0
#
#         while left < right:
#             val_left, val_right = height[left], height[right]
#             if val_left > val_right:
#                 if max_right < val_right:
#                     # 새로운 가장 높은 지점을 찾은 경우
#                     # 물이 채워지지 않고 값만 업데이트
#                     max_right = val_right
#                 else:
#                     # 현재 지점은 다른 두 높은 건물에 쌓여있음
#                     # 이 떄 왼쪽은 아까 포인터가 가리킨 벽이 있고
#                     # 오른쪽은 maxRight가 있음.
#                     ret += (min(max_right, val_left) - val_right)
#                 right -= 1
#             else:
#                 if max_left < val_left:
#                     max_left = val_left
#                 else:
#                     ret += (min(max_left, val_right) - val_left)
#                 left += 1
#         return ret