leetcode Trapping Rain Water 문제풀기

#[leetcode][42] Trapping Rain Water 문제풀기!

• 문제풀러가기✈

👓 문제 요약

내가 말이야.. 특이한 목욕탕을 만들고 싶거든.. 근데 물이 얼마나 필요할지 잘 모르겠어.. 니가 좀 구해줄래?

자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기

🔑 문제 풀이

대표적으로 이런 문제는 대부분 2 pointer 문제더라!!

일단 물 높이를 생각해봅시다!!. 인풋이 [2 ,0 ,0 ,3] 이렇게 주어지면, 왼쪽 기둥은 높이가 2, 오른쪽 기둥은 3 이다. 따라서 물을 다 채우면 왼쪽이 오른쪽 보다 낮기 때문에 높이 2까지만 채워집니다.

이 원리를 이용해 왼쪽에서 오른쪽 방향으로 하나씩 참고하는 포인터와 반대로 오른쪽에서 왼쪽 방향으로 참고하는 포인터를 생성합니다!.

만약 왼쪽에서 하나씩 보다가 현재 기둥이 오른쪽에서 참조하는 기둥의 높이보다 낮거나 같으면 한 칸 물을 채워주고, 반대로 오른쪽 기둥이 더 낮으면 오른쪽에서 물을 채워주는 형식으로 진행합니다. 채워주는 양은 현재 물의 높이 - 현재 기둥의 높이라고 생각하면 되겠습니다!. 물을 낮은 곳 부터 차근차근 채워나간다고 생각하면 편하겠군요.

왼쪽에서 먼저가던 오른쪽으로 가던 어느쪽으로 기준을 잡던 상관이 없지만 저는 왼쪽으로 기준 삼았습니다!.

그래서 제가 어떻게 풀었냐면 !!

물을 채울 때 높이가 가장 중요하다. 물의 높이는 왼쪽 기둥과 오른쪽 기둥의 높이를 비교하여 낮은 값과, 이때까지 물의 높이 중 더 큰 값을 선택하면 됩니다. 알아보기 쉽게 다음과 같이 표현했습니다.

Math.max(fixH, Math.min(height[left], height[right]));
// fixH가 물의 높이다.

그런 다음 왼쪽 오른쪽 어디를 채울지 선택해 채우면 된다!!.!

🥽 소스코드 및 소스해석

var trap = function (height) {
  let answer = 0;
  let left = 0;
  let right = height.length - 1;
  let fixH = 0;
  while (left < right) {
    fixH = Math.max(fixH, Math.min(height[left], height[right]));
    if (height[left] <= fixH) {
      answer += fixH - height[left];
      left++;
    } else {
      answer += fixH - height[right];
      right--;
    }
  }
  return answer;
};

🔨 문제 후기

재미있다.

처음에 저는 상당히 긴 코드를 작성했었습니다. 제가 워낙 설계하지 않고 풀다보니 깔끔하게 풀지를 못해서 중간에 값을 변경하고 또 변경하다가 문제를 통과했습니다.

다른분들이 푼 아주 깔끔한 소스를 보고 약간의 자괴감이 드는 한편 또 깨닳음이 있었습니다.

코드가 간결해 질수록 버그도 적어진다!!

앞으로 간결하게 코드를 작성하도록 노력해야할 듯 합니다 !!