빗물 트래핑

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

Trapping Rain Water - LeetCode

주어진 height를 가지고 해당 블럭들 안에 물이 고인다면 최대 얼만큼의 물이 고일 수 있는지 계산하는 문제이다.

 

예제 1.

입력 

height = [0,1,0,2,1,0,1,3,2,1,2,1]

출력

6 

 

매우 어려운 문제이다. 

스택 등 여러 방법을 적용해 보았지만 쉽게 풀리지 않아 결국 정답을 참고하게 되었다.

 

풀이

# 높이를 받아 비온후 얼마나 많은 물이 쌓일 수 있는지 계산하라.
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]


def trap(height):
    if not height:
        return 0
    volume = 0
    # 투포인터 배정
    left, right = 0, len(height) - 1
    # 왼쪽, 오른쪽의 가장 큰 높이 값 배정
    left_max, right_max = height[left], heights[right]

    # left가 right보다 크거나 같게 되면 이는 둘이 엇갈린 것임
    while left < right:
        # 찾으면서 계속 현재 높이와 가장 높았던 높이를 비교하며 항상 최고값만 오도록 한다.
        left_max, right_max = max(height[left], left_max), max(height[right], right_max)

        # 왼쪽 포인터는 오른쪽으로 오른쪽 포인터는 왼쪽으로 움직이며 이에 대한 단차 정도를 찾고 volunm에 더함
        if left_max <= right_max:
            volume += left_max - height[left]
            left += 1
        else:
            volume += right_max - height[right]
            right -= 1

    return volume


print(trap(heights))

 

가장 쉬운 방법은 투포인터 방식이다.

왼쪽, 오른쪽 끝에 포인터를 두고 가장 높은 위치를 향해 좁혀 나간다. 

이때 왼쪽 max와 오른쪽 max height를 지정해가며 더 큰쪽의 방향으로 움직인다 ( 왼쪽 max보다 오른쪽 max가 크거나 같다면 왼쪽 포인터를 이동 ), 이렇게 되면 가장 높은 위치에서 왼쪽, 오른쪽 포인터가 만나게 된다.

 

가장 높은 위치로 가는 과정에서 현재의 높이 ( 포인터의 높이 )와 그 때 까지의 max( 왼쪽과 오른쪽 )의 차이 만큼을 계산하여

volume에 더한다.