08 빗물 트래핑

높이를 입력 받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라

My solution

leftMax를 왼쪽에서의 최대 높이로 하고, rightMax를 오른쪽에서 최대 높이로 해서 투포인터 알고리즘으로 풀이했다. while문은 left가 right보다 작은동안 반복되고 높이 배열에 포인터를 인덱스로 줬을 때 오른쪽 높이가 더 크다면 left를 증가시키고 반대면 right를 증가시켰다.

left, right 포인터가 달라짐에 따라 두 max에 더 작은 높이가 들어오면 amountOfWater에 차가 누적된다.

leftMax, rightMax의 값은 물의 양을 누적한 뒤에 현재 포인터가 위치한 곳의 높이를 가지고 다시 업데이트해준다.

h : [0, 1, 0, 2, 1]

이 간단한 테스트케이스를 보면 left, right포인터가 범위를 조정하는 순서가

left: 1, right: 4 // <= h[0] : 0 < h[4] : 1

left: 1, right: 3 // <= h[1] : 1 == h[4] : 1 left가 가리키는 높이가 더 작거나 같으면 right가 줄어든다.

left: 2, right: 3 // <= h[1] : 1 < h[3] : 2 leftMax가 1이 된 상태에서 left가 가리키는 높이가 0이 되어서 물의 양이 1 추가된다.

left: 3, right: 3 // <= h[2] : 0 < h[3] : 2

으로 변화할 것을 알 수 있다.

Code

const TrappingRainWater = function (h) {
  let left = 0;
  let right = h.length - 1;
  let amountOfWater = 0;
  let leftMax = h[left];
  let rightMax = h[right];

  while (left < right) {
    if (h[left] < h[right]) {
      left++;
      amountOfWater += Math.max(0, leftMax - h[left]);
      leftMax = Math.max(leftMax, h[left]);
    } else {
      right--;
      amountOfWater += Math.max(0, rightMax - h[right]);
      rightMax = Math.max(rightMax, h[right]);
    }
  }

  return amountOfWater;
};
JavaScript
복사

금방 풀이를 생각해내기 쉽지 않은 문제다.

Solution

1. 투 포인터를 최대로 이동

높이와 너비를 모두 살펴보면 O(n^2)이다. 투 포인터는 O(n)이다.

가장 높이가 높은 막대를 좌우를 가르는 장벽 역할로 한다.

이 막대가 될 때까지는 left_max와 right_max는 각각의 현재 높이의 차이만큼 volume을 더해간다.

이렇게 되면 낮은 쪽이 항상 채워진다. 결국 최대 높이 막대에서 만나고 반복이 종료된다.

높이가 0일 때는 계산할 필요도 없어서 처리해준 점이 더 좋았고, 현재 높이를 비교한 다음 포인터를 먼저 이동시켜주는 내 방식과 다르게 왼쪽, 오른쪽의 최대 높이를 먼저 업데이트한 뒤 그 값을 비교해서 오른쪽 막대가 같거나 더 클 때는 왼쪽의 현재 높이와 최대 높이를 뺀 값을 물의 양에 누적시킨다음 포인터를 이동했다. js로 구현하면 아래와 같다.

const TrappingRainWater = function (h) {
  if (h.length === 0) return 0;

  let volume = 0;
  let left = 0;
  let right = h.length - 1;
  let leftMax = h[left];
  let rightMax = h[right];

  while (left < right) {
    leftMax = Math.max(h[left], leftMax);
    rightMax = Math.max(h[right], rightMax);

    if (leftMax <= rightMax) {
      volume += leftMax - h[left];
      left++;
    } else {
      volume += rightMax - h[right];
      right--;
    }
  }
  return volume;
};
JavaScript
복사

2. 스택 쌓기

현재 높이가 이전 높이보다 높을 때 격차만큼 물 높이를 채운다. 변곡점을 만날 때마다 스택에서 꺼내서 차이를 volume에 누적했다.

스택을 한 번만 보므로 O(n)이다.

while문에서는 stack에 이전 값(인덱스)이 존재하고, 현재 높이가 이전 높이보다 높을 때 물높이를 계산해서 누적한다. js로 구현하면 아래와 같다.

const TrappingRainWater = function (h) {
  const stack = [];
  let volume = 0;
  for (let i = 0; i < h.length; i++) {
    while (stack.length > 0 && h[i] > h[stack[stack.length - 1]]) {
      const top = stack.pop();
      if (stack.length === 0) break;

      const distance = i - stack[stack.length - 1] - 1;
      const water = Math.min(h[i], h[stack[stack.length - 1]]) - h[top];

      volume += distance * water;
    }
    stack.push(i);
  }
  return volume;
};
JavaScript
복사