[leetcode][42] Trapping Rain Water

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

---

땅의 고도를 나타내는 배열이 주어질 때, 비가 내린 후 가둘 수 있는 물의 양을 구해라.

---

예시로 주어진 [0,1,0,2,1,0,1,3,2,1,2,1] 을 한 번 살펴보자.

예시의 5 인덱스를 보면 가둘 수 있는 물의 양은 양 옆에 있는 고도가 아닌 인덱스 5를 기점으로 왼쪽에 있는 고도 중 가장 높은 것(leftMax)과 오른쪽에 있는 고도 중 가장 높은 것(rightMax)이 관계가 있다.

leftMax와 rightMax를 구했다면 이들 중 더 낮은 고도 - 탐색 중인 고도가 가둘 수 있는 물의 양이다.

인덱스 5를 예로 들면 leftMax = 2(index 3). rightMax = 3(index 7). 이 되고 이들 중 더 낮은 고도는 2다. 그리고 현재 고도는 0(index 5)이므로 인덱스 5에서 가둘 수 있는 물 양은 2가 된다. 만약 leftMax, rightMax 보다 현재 고도가 같거나 더 높다면 가둘 수 있는 물의 양은 0이다. (ex. index 7)

 

leftMax, rightMax를 구하기 위해 왼쪽에서부터 탐색하면서 가장 높은 고도를 저장하는 배열과, 오른쪽에서부터 탐색하면서 가장 높은 고도를 저장하는 배열을 구한다.

 

heights(고도) = [0,1,0,2,1,0,1,3,2,1,2,1]

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

rightMaxArray = [3,3,3,3,3,3,3,3,2,2,2,1]

 

i번째 인덱스의 물의 양을 구할 때, leftMax = leftMaxArray[i-1], rightMax = rightMaxArray[i+1]이 된다.

그리고 i번째 인덱스의 가둘 수 있는 물의 양은 min(leftMax, rightMax) - heights[i] 가 된다.

heights[i]가 leftMax, rightMax 보다 같거나 크다면 0.

 

시간복잡도는 선형복잡도인 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/42.%20Trapping%20Rain%20Water.cpp