반응형
[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))
💡 핵심 아이디어: "양쪽에서 중앙으로 이동하며 작은 쪽을 기준으로 계산"
- leftMax와 rightMax를 유지하면서 한 번의 순회로 해결
- 작은 쪽(leftMax 또는 rightMax)을 기준으로 물을 계산
- 양쪽 끝에서 중앙으로 이동하면서 빗물을 계산 (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 설명
0 | 11 | 0 | 1 | 0 | height[left] < height[right], 왼쪽 이동 |
1 | 11 | 1 | 1 | 0 | height[left] >= height[right], 오른쪽 이동 |
1 | 10 | 1 | 2 | 0 | height[left] < height[right], 왼쪽 이동 |
2 | 10 | 1 | 2 | 1 | water += 1 - height[2] |
3 | 10 | 2 | 2 | 1 | height[left] >= height[right], 오른쪽 이동 |
3 | 9 | 2 | 2 | 2 | water += 2 - height[9] |
3 | 8 | 2 | 2 | 2 | height[left] >= height[right], 오른쪽 이동 |
3 | 7 | 2 | 3 | 2 | height[left] < height[right], 왼쪽 이동 |
✅ 최종 결과: 6 (가둘 수 있는 물의 양)
📌 시간 복잡도 분석
접근법 시간 복잡도 설명
Brute Force (O(N²)) | O(N²) | 매번 Math.max() 호출로 인해 비효율적 |
Two Pointers (O(N)) | O(N) | 한 번의 순회만으로 해결 |
✅ Two Pointers 사용하면 O(N)으로 해결 가능! 🚀
📌 최종 정리
- 각 위치에서 고일 수 있는 물의 양 = min(leftMax, rightMax) - height[i]
- 모든 인덱스에서 leftMax와 rightMax를 찾는 것은 O(N²)로 비효율적
- "양쪽 끝에서 중앙으로 이동하면서 작은 쪽을 기준으로 물을 계산"하면 O(N)으로 해결 가능
- O(N) 탐욕법(Two Pointers)로 해결 가능!
💡 이제 비슷한 문제에서 "양쪽에서 중앙으로 이동하는 방식"을 떠올려 보세요! 🚀
반응형
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode 134] Gas Station - 탐욕법(Greedy)으로 해결하기 (0) | 2025.03.13 |
---|---|
[LeetCode 238] Product of Array Except Self - 나누기 없이 배열 곱셈 구하기 (0) | 2025.03.12 |
[LeetCode 380] Insert Delete GetRandom O(1) - 효율적인 데이터 구조 구현 (Set vs. Array + Map) (0) | 2025.03.11 |
[LeetCode 274] H-Index - 연구 논문의 영향력 측정 (탐욕법 + 정렬) (0) | 2025.03.10 |
[LeetCode 45] Jump Game II - 최소 점프 횟수 찾기 (탐욕법 + DP) (0) | 2025.03.09 |