❓문제

42.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:

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.

밑변(X값)이 1이라는 너비를 가지는 그래프가 존재한다고 가정할 때, X(index)값에 따른 Y값(array)이 존재하는 Array가 주어진다. 주어진 Array는 특정한 지형(?)을 형성하고 그 지형에 물을 가둔다고 생각해볼 때, 물의 전체 면적을 구하는 문제이다. 그림과 예시를 보면 좀 더 이해가 잘 될 것이다.

💡풀이

var trap = function(height) {
    let peak = Math.max(...height)
  let block=0
  for(let i=peak;i>0;i--) {
    let vacancy=[];
    for(let p=0;p<height.length;p++){
      if(height[p]>=i) {
        vacancy.push(p)
      }}
        for(let f=0;f<vacancy.length;f++){
          if(!(vacancy[f+1]-vacancy[f]-1)==false)
          block+=(vacancy[f+1]-vacancy[f]-1)
        }
  }
  return block
};

description

풀이의 로직은 이러하다.

"가장 높은 지점(peak)을 구해서 그 지점에서부터 X축에 평행하는 선을 그어서, 한칸씩 내려오며(1st for문) 모든 array값과의 교점을 구한다.(2nd for문) 그리고 각 교점의 사이공간(물이 차있는 공간)의 길이를 총합한다(3rd for문)"

총 3번의 for문을 써서 모든 그래프 공간을 가로로 잘라서 그중에 물이 차있는 공간을 구하는 적분 비스무리한 방법이다. 좀 무식한 방법이지만, 답이 맞게 나왔고, 신이나서 submit을 하였으나, leetcode측에서 넣은 값은 엄청나게 큰 숫자가 가득한 Array였고, 결과는 Time Limit Exceed였다. 즉 내가 짠 로직은 답은 맞을지언정 비효율적인 코드라는 뜻이다.

leetcode hard를 풀었다는 엄청난 쾌감도 Time Limit Exceed에 막혀 이내 수그러 들어버렸지만, 반쪽자리 성취감이라도 기록하기 위해 글을 쓴다. 곧 다시 풀어낼거다, 기다려라!