[Python] LeetCode 42. Trapping Rain Water

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

Trapping Rain Water - LeetCode

왼쪽 끝 / 오른쪽 끝에서부터 각각 가운데로 이동하면서

"최대 높이 - 현재 높이" 순으로 값을 더하는 식으로 풀 수 있는 문제.

왼쪽의 최대높이와 오른쪽의 최대높이를 비교해서, 더 작은 쪽을 가운데로 이동시킨다.

 

 

cf. 이 풀이는 아래 책에서 제공한 코드를 참고했습니다.

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기

 

	class Solution:
	def trap(self, height: List[int]) -> int:
	if not height:
	return 0
	result = 0
	# 왼쪽 / 오른쪽의 idx 지정
	left, right = 0, len(height)-1
	# 왼쪽 / 오른쪽의 최고높이 결정
	left_height, right_height = height[left], height[right]
	while left < right:
	# 현재 위치 기준으로 왼쪽 / 오른쪽 높이 최댓값 경신
	left_height, right_height = max(left_height, height[left]), max(right_height, height[right])
	# left 높이가 right보다 작거나 같을 경우 left idx 이동
	if left_height <= right_height:
	result += left_height - height[left]
	left += 1
	else:
	# right idx 이동
	result += right_height - height[right]
	right -= 1
	return result

view raw [LeetCode] Trapping Rain Water.py hosted with ❤ by GitHub