[LeetCode] Trapping Rain Water

문제

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

 

Approach

처음에 어떻게 접근해야하나 고민을 좀 했다. 순차적으로 읽다가 벽을 만나면 다음 벽 만날 때 까지 탐색해서 해야하나... -> 경우의 수가 너무 많아져서 안됨

결론은 현재 접근해 있는 index 바로 위에 물이 얼마나 담기는 지를 파악해 답에다 다 더하는 것이었다.

Brute Force로는 배열을 순차적으로 탐색하며 현재 index에서 왼쪽으로 다시 돌아가 가장 높은 왼쪽 벽 구하기, 그 다음 오른쪽으로 가서 가장 높은 오른 쪽 벽 구하기 -> (다음 두 높은 벽중 낮은 벽 - 현재 index의 벽 높이)를 답에 더해줌.

이를 모든 index마다 다 해서 O(n^2)만에 풀 수 있다.

이 때 i번째 index 왼쪽에서 가장 높은 벽을 leftMax배열에 저장하고, 오른쪽에서 가장 높은 벽을 rightMax배열에 저장하는 DP를 사용하면

O(n)만에도 풀 수 있다.

 

Optimization

사실 꼭 좌우에서 가장 높은 벽을 찾아 비교해야 할 필요는 없다.

물 양 계산을 위해 양 옆의 탐색한 부분까지에서 가장 높은 벽의 높이는 알고 있어야 하지만 한 쪽이 한 쪽보다 높기만 하면 물이 담아지기 때문.

따라서 배열을 각각 왼쪽 끝, 오른쪽 끝에서 부터 탐색하는 2개의 포인터를 만들고

어느 한 쪽이 다른 한 쪽 보다 높아지면 (그 쪽에서 지금까지 가장 높은 벽) - (현재 벽의 높이)를 답에 더하고 배열을 탐색한다.

https://leetcode.com/articles/trapping-rain-water/4번

Trapping Rain Water

Code

1.DP

https://github.com/chi3236/algorithm/blob/master/LeetCode_TrappingRainWater.cpp

chi3236/algorithm

2. Two Pointers

https://github.com/chi3236/algorithm/blob/master/LeetCode_TrappingRainWater_TwoPointers.cpp

chi3236/algorithm