.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.
Plain Text
복사
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Plain Text
복사
Constraints:
•
n == height.length
•
1 <= n <= 2 * 10^4
•
0 <= height[i] <= 10^5
My solution
각 막대의 너비가 1인 고도 지도를 나타내는 n개의 음이 아닌 정수가 주어졌을 때, 비가 온 후 얼마나 많은 물을 가두어 놓을 수 있는지 계산한다.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.
Plain Text
복사
위 고도 지도(검은색 단면)는 배열 [0,1,0,2,0,1,3,2,1]로 표시된다. 이 경우 빗물 6단위(파란색 부분)가 갇히고 있다.
왼쪽, 오른쪽 끝에 포인터를 배치하고,
왼쪽의 경우는 leftMax를 두어서 최대 높이와 그보다 작은 높이의 차를 water에 계속 더해넣는다.
if(height[left] >= leftMax){
leftMax 업데이트
} else {
water += leftMax - height[left];
}
JavaScript
복사
오른쪽 경우에도 로직은 동일하다. rightMax를 사용한다.
그리고 이 두 로직은 height[left] < height[right] 조건 내에서 height[right]가 더 큰 경우 위의 로직이 실행되고 반대의 rightMax 로직이 실행된다.
두 포인터의 움직임은 최대 높이를 향해 움직여서 만나는 것을 전제로 하기 때문에 height[right]인 경우에는 leftMax로직과 함께 left++를 실행하는 것이다.
이렇게 포인터를 이동시키다보면 높이차를 구해서 water에 모두 누적시킨 다음 최대 높이에서 포인터가 멈춘다.
hard 난도의 문제이다보니 설계하는 것이 쉽지는 않았다.
이전 높이보다 현재 높이(height[left], height[right])가 더 높아진다고 하더라도 이전 높이 중에 이보다 더 높은 높이가 있어야만(leftMax, rightMax) water를 누적시킬 수 있다.
Code
/**
* @param {number[]} height
* @return {number}
*/
const trap = function (height) {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
};
describe('trap', () => {
// it('TC1', () => {
// expect(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])).toStrictEqual(6);
// });
// it('TC2', () => {
// expect(trap([4, 2, 0, 3, 2, 5])).toStrictEqual(9);
// });
it('TC3', () => {
expect(trap([0, 1, 0, 2, 1, 2])).toStrictEqual(2);
});
});
JavaScript
복사
