반응형
1. 문제
https://leetcode.com/problems/trapping-rain-water/
Trapping Rain Water - LeetCode
Can you solve this real interview question? 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 can trap after raining. Example 1: [https://assets.leetcode.com/upl
leetcode.com
2. 코드
풀이 과정을 생각하기 정말 어려운 문제인 것 같다. 그래서 Hard 이구나... 정답을 보고 이해했다 ㅠㅠ
풀이의 핵심은 값을 누적하는 방식을 사용하는 것이 아닌 각각의 요소의 왼쪽, 오른쪽 최대값을 저장하여 각 요소마다 계산 로직이 굴려야 하며(?), 해당 요소가 물이 담긴 요소인지 아닌지는 계산 로직을 통해 판별된다는 것이다. 만약 해당 요소가 물이 담긴 요소가 아니라면(벽이라고 생각하면 편하다) 계산 결과 값이 0이 나오고, 물이 담긴 요소(물 부분이라고 생각하면 편하다)라면 1 이상의 값이 나온다.
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let maxLeft = 0;
// 각 요소 기준 왼 쪽에 있는 요소 중 가장 큰 값을 저장한다.
let left = new Array(height.length).fill(0);
for(let i = 0; i < height.length; i++) {
if(maxLeft < height[i]) {
maxLeft = height[i];
}
left[i] = maxLeft;
}
let maxRight = 0;
// 각 요소 기준 오른 쪽에 있는 요소 중 가장 큰 값을 저장한다.
let right = new Array(height.length).fill(0);
for(let i = height.length-1; i >= 0; i--){
if(maxRight < height[i]) {
maxRight = height[i];
}
right[i] = maxRight;
}
let trap = 0;
// 왼 편 큰 값, 오른 편 큰 값 중 작은 값에서 현재 요소 값을 뺀다.
for(let i = 0; i < height.length; i++) {
trap += Math.min(left[i], right[i]) - height[i];
}
return trap;
};
이해에 참고한 글)
반응형