[파이썬 알고리즘 인터뷰] 배열 - 빗물 트래핑

문제설명

- 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

예시

 

#입력

[0,1,0,2,1,0,1,3,2,1,2,1]

#출력
6

 

풀이

left는 height 배열 왼쪽부터 시작을 하고 right는 배열 오른쪽부터 시작을 한다.

left_max 와 right_max는 height 배열의 원소값이다. 

둘의 값을 비교하여서 left값이 더 작거나 같을 때는 left 배열값을 1 더해주어 점점 오른쪽으로 이동을하고 반대로

left값이 더 클경우 right 배열값을 1감소시켜 왼쪽으로 이동 시킨다.

비교를 하면서 좌우 기둥 최대높이 Left_max, right_max가 현재높이와의 차이만큼 물높이 volume 을더해나간다.

 

def trap(height):

    volume = 0
    left, right = 0,len(height) - 1
    left_max, right_max = height[left], height[right]

    print(left)
    print(right)

    while left < right: #배열의 순서가 작을때
        left_max, right_max = max(height[left], left_max), max(height[right], right_max)
        print('left_max' ,left_max ,'right_max', right_max)
        if left_max <= right_max:
            print('height[left] : ',height[left] )
            volume += left_max - height[left]
            print('volume ',volume)
            left += 1
        else:
            print('height[right] : ', height[right])
            volume += right_max - height[right]
            print('volume ', volume)
            right -= 1
    return volume


height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap(height))

출력

/Users/hamyeong-gwan/opt/anaconda3/envs/ptu/bin/python /Users/hamyeong-gwan/Desktop/PYTHON/알고리즘/trapping_rain_water.py
0
11
left_max 0 right_max 1
height[left] :  0
volume  0
left_max 1 right_max 1
height[left] :  1
volume  0
left_max 1 right_max 1
height[left] :  0
volume  1
left_max 2 right_max 1
height[right] :  1
volume  1
left_max 2 right_max 2
height[left] :  2
volume  1
left_max 2 right_max 2
height[left] :  1
volume  2
left_max 2 right_max 2
height[left] :  0
volume  4
left_max 2 right_max 2
height[left] :  1
volume  5
left_max 3 right_max 2
height[right] :  2
volume  5
left_max 3 right_max 2
height[right] :  1
volume  6
left_max 3 right_max 2
height[right] :  2
volume  6
6

Process finished with exit code 0