수달씨의 개발공간

[LeetCode] Trapping Rain Water - 효율적인 해결 방법 (Two Pointers)

📌 문제 설명

LeetCode의 "Trapping Rain Water" 문제는 높이 배열(height[])이 주어질 때, 빗물이 고일 수 있는 총량을 계산하는 문제입니다.

• height[i]: 각 기둥의 높이
• 각 기둥의 너비는 1로 고정
• 빗물이 얼마나 고일 수 있는지 계산해야 함

📌 문제 해결 과정

✅ 잘못된 접근 (Brute Force, O(N²))

모든 인덱스에서 왼쪽 최대(leftMax)와 오른쪽 최대(rightMax) 를 찾아 빗물을 계산하는 방법이 떠오를 수 있습니다.

export function trap(height: number[]): number {
  let water = 0;

  for (let i = 1; i < height.length - 1; i++) {
    const leftMax = Math.max(...height.slice(0, i + 1));
    const rightMax = Math.max(...height.slice(i));

    water += Math.max(0, Math.min(leftMax, rightMax) - height[i]);
  }

  return water;
}

🚨 문제점:

• Math.max(...arr)를 반복 호출해야 하므로 시간 복잡도 O(N²) 발생
• 배열이 길어질수록 매우 비효율적

📌 최적화된 해결 방법 (Two Pointers, O(N))

💡 핵심 아이디어: "양쪽에서 중앙으로 이동하며 작은 쪽을 기준으로 계산"

1. leftMax와 rightMax를 유지하면서 한 번의 순회로 해결
2. 작은 쪽(leftMax 또는 rightMax)을 기준으로 물을 계산
3. 양쪽 끝에서 중앙으로 이동하면서 빗물을 계산 (O(N))

✅ 작은 쪽을 기준으로 계산하는 이유:

• leftMax < rightMax라면 leftMax보다 높은 곳이 나오기 전까지 leftMax가 현재 위치에서 최대 물 저장 가능 높이
• 반대로 rightMax < leftMax라면 rightMax가 현재 위치에서 최대 물 저장 가능 높이

📌 최적화된 코드 (O(N))

export function trap(height: number[]): number {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;

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

  return water;
}

📌 예제 분석

입력:

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

Step-by-step 실행 과정

left right leftMax rightMax water 설명

✅ 최종 결과: 6 (가둘 수 있는 물의 양)

📌 시간 복잡도 분석

접근법 시간 복잡도 설명

✅ Two Pointers 사용하면 O(N)으로 해결 가능! 🚀

📌 최종 정리

1. 각 위치에서 고일 수 있는 물의 양 = min(leftMax, rightMax) - height[i]
2. 모든 인덱스에서 leftMax와 rightMax를 찾는 것은 O(N²)로 비효율적
3. "양쪽 끝에서 중앙으로 이동하면서 작은 쪽을 기준으로 물을 계산"하면 O(N)으로 해결 가능
4. O(N) 탐욕법(Two Pointers)로 해결 가능!

💡 이제 비슷한 문제에서 "양쪽에서 중앙으로 이동하는 방식"을 떠올려 보세요! 🚀