LeetCode No.42 - Trapping Rain Water

카테고리: Algorithms

January 17, 2022

문제링크

접근

먼저, 특정 칸 height[i]에 물을 채우기 위한 조건을 생각해보면 다음과 같습니다:

물을 채우기 위한 조건
물을 채우기 위한 조건

위 그림과 같이, height[i]에 채울 수 있는 물의 양은 왼쪽에 있는 블럭들 중 가장 높은 블록의 높이 leftMax와 오른쪽 블럭들 중 가장 높은 블록의 높이 rightMax에 대해 둘 중 더 낮은 높이 - 현재 블록의 높이로 계산됩니다.

이에 착안하여, left, right 두 개의 포인터를 이용해 leftMax, rightMax 중 더 낮은 쪽이 높은쪽으로 움직이도록 하면 정답을 구할 수 있습니다. 결과적으로 이렇게 하면 높이가 가장 높은 블록쪽으로 두 개의 포인터가 모이게 되겠지요:

두 개의 포인터가 움직이는 모습
두 개의 포인터가 움직이는 모습

만약 가장 높은 블록이 여러 개라면 그 중 하나의 블록으로 모이게 됩니다.

자바스크립트 구현

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