Trapping Rain Water
- 문제
- 링크
- 주어진 그래프에서 비가 온다면 물을 얼마나 담을 수 있는지 구하기
- 생각해볼 수 있는 것
- 막대와 막대 사이에 공간이 있다면 물을 넣을 수 있다
- 풀이
- 2 pointer 를 활용하기
- 왼쪽 끝, 오른쪽 끝을 비교하면서 둘 사이를 좁혀간다
- 인덱스를 이동하면서 더 낮은 막대를 기준으로 처음 인덱스부터 마지막 인덱스까지 물을 채워 넣는다
- 레벨이라는 변수를 이용해서 현재 물이 어느 높이까지 채워져 있는지 체크한다
- 왼쪽과 오른쪽 중에 높이가 더 작은 막대의 포인터를 이동한다
- 높이가 더 작은 막대만큼 물은 들어가지 않으므로 채워져 있는 물에서 해당 막대의 높이만큼 빼준다
- 결과적으로 모든 물이 채워져 있는 상태에서 막대만큼 물을 빼주기 때문에 정답이 된다
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1, level = 0, answer = 0;
while(left < right) {
int lH = height[left], rH = height[right];
if(level < Math.min(lH, rH)) {
answer += (right - left) * (Math.min(lH, rH) - level);
level = Math.min(lH, rH);
}
if(lH < rH) {
answer-=Math.min(lH, level);
left++;
}
else {
answer-=Math.min(rH, level);
right--;
}
}
return answer;
}
}
