Trapping rain water

문제: https://leetcode.com/problems/trapping-rain-water/

위의 막대 그래프처럼 input으로 막대 그래프의 높이가 주어진다. 막대그래프 사이에 비가 왔을 때 쌓인 빗물의 양(파란색 칸)을 구하는 문제이다.

2가지 방법으로 해결이 가능하다. 처음에는 내가 해결한 방법이고 두번째는 투 포인터로 해결한 방법이다.

해결방법1

임시 배열에 넣어서 그 상황에 따라 처리하는 방법

어떤 알고리즘으로 풀었는지는 잘 모르겠지만.. 그냥 요구사항에 맞춰서 차근차근 진행한 풀이이다.

문제를 해결하기 앞서 이 이 방법은 height배열을 앞에서 부터 순회하면서 각 높이를 순회할 때 변화하는 모습을 보고 생각해 낸 방법이다. 간단한 배열을 예시로 어떻게 구현되는지 설명하겠다.ㅇ

ex)
[2,1,0,1,3]
=> [2]
=> [2,1]
=> [2,1,0]
=> [2,1,0,1] //여기서 0자리에 한칸이 쌓일 수 있다.
=> [2,1,1,1] //배열 업데이트
=> [2,1,1,1,3] //여기서 1인 3개가 2로 변한다.
=> [2,2,2,2,3] //배열 업데이트

위와 같은 식으로 stack의 마지막 값과 크기를 비교해 배열 내부의 값을 변경시켜주는 방식으로 구현했다.

• stack : 배열에 height를 순회하면서 위의 예시처럼 쌓아줄 것이다.

1. height를 순회하며 스택의 마지막 값과 현재 값을 비교해 상황에 맞게 처리한다.

• 스택의 마지막 값 > 현재 값(h) : stack에 넣어준다. - stack.push(h)
• 마지막값 <= 현재 값(h) : stack에 넣어주고, 위의 예시처럼 stack을 업데이트 해주고 water에 더해준다. - calc() 이용
  -> 만약 스택의 첫번째 값보다 크다면 새로운 스택이 시작 해야된다. -> why? 현재 블럭이 더 높다는 것이기 때문에 앞에 블럭은 뒤에 올 블럭에 영향을 주지 못하기 때문이다.

calc(stack)

stack을 업데이트 해주고 answer에 더해줄 stack에서 몇 칸이 채워졌는지 (물이 얼마나 채워졌는지)를 반환해준다.

• min : 스택의 첫번째, 마지막 값 중 가장 작은 값
  = water : 물이 채워지는 양

min 값보다 작은 값들은 min으로 변경시켜주고 그 차이만큼 water에 더해준다.

code

const trap = (height) => {
  let water = 0;
  let stack = [height.shift()];
  for (let h of height) {
    if (stack[stack.length - 1] < h) {
      stack.push(h);
      water += calc(stack);
      if (stack[0] < h) stack = [h];
    } else {
      stack.push(h);
    }
  }
  return answer;
};

const calc = (stack) => {
  let water = 0;
  const min = Math.min(stack[0], stack[stack.length - 1]);
  for (let i = 1; i < stack.length - 1; i++) {
    if (stack[i] < min) {
      water += min - stack[i];
      stack[i] = min;
    }
  }
  return water;
};

해결방법 2

2개의 포인터를 갖고 진행하는 것이다.

• left : 맨 처음부터 시작
• right : 맨 마지막 값부터 시작
• maxLeft: left가 진행해 온 블럭 중 가장 높은 블럭
• maxRight: right가 진행해온 블럭 중 가장 높은 블럭

maxLeft,maxRight를 비교해 작은 값 부분에서 아래에 주어지는 계산을 실행해 간다.

if (maxLeft <= maxRight) {
  water += maxLeft - height[left];
  left++;
} else {
  water += maxRight - height[right];
  right--;
}

• why? maxLeft,maxRight 중 작은 값에서 진행하는 이유
  예시를 들어서 보면 이해가 된다.
  ex) 아래의 배열을 예시로 무조건 왼쪽에서 실행해보면
  [3,1,2,1,2]
  1번 인덱스 1에서 maxLeft(3)과 비교해 water에 넣어준다면 실제로 저곳에는 water에 1만 차오르는 데 2나 차오르게 된다. 즉 가장 높은 블럭과 비교하게 될 수도 있기 때문에 maxLeft와 maxRight 중 작은 쪽에서만 실행해 주는 것이다.

code

const trap = (height) => {
  let water = 0;
  let [left, right] = [0, height.length - 1];
  let [maxLeft, maxRight] = [height[left], height[right]];

  while (left < right) {
    maxLeft = Math.max(maxLeft, height[left]);
    maxRight = Math.max(maxRight, height[right]);

    if (maxLeft <= maxRight) {
      water += maxLeft - height[left];
      left++;
    } else {
      water += maxRight - height[right];
      right--;
    }
  }

  return water;
};

마무리

문제를 보고 차근차근 상황에 맞게 변화하는 과정을 추적해 나가서 해결할 수 있었다.

leetcode에는 코드에 따라 시간효율성 같이 걸린 시간이 나오는데 첫번째 풀이방법은 빠르지 않았다. 그리고 처음 stack에 맨 첫값을 넣어줄 때 shift()를 사용해줬는데 shift()를 사용하지 않을 때 보다 속도가 유효하게 차이나는 것을 확인할 수 있었다.

코딩테스트에서는 정답 뿐아니라 효율성도 중요하기 때문에 shift()는 효율성검사가 있는 문제에서는 사용을 하면 안될 것 같다.

투포인터로 해결하는 방법이 가장 빠른 시간결과가 나왔다. 투포인터로 해결하는 방법은 스스로는 한번도 생각해서 풀어보지 않았어서 어색했다. 투포인터가 효율적인 만큼 앞으로 문제를 해결할 때 투포인터로 해결 가능한지 고려해봐야겠다.

파이썬 알고리즘 인터뷰 라는 책을 보면서 진행하고 있는데 효율적인 풀이를 배울 수 있어서 참 좋은 것같다.

참조

• 파이썬 알고리즘 인터뷰 - 책