Trapping Rain Water
막대들이 나란히 늘어서 있으며, 각각의 너비는 1단위입니다. height[i]는 막대 i의 높이입니다. 빗물은 막대 사이의 낮은 곳에 고입니다. 더 높은 막대가 왼쪽 어딘가와 오른쪽 어딘가에 모두 있을 때만 막대 위에 물이 고이며, 첫 번째 막대와 마지막 막대 바깥으로는 물이 흘러내립니다. 이 줄에 담기는 물의 총 단위 수를 반환하세요.
함수
- heightinteger-array
- 왼쪽에서 오른쪽으로 각 막대의 높이
- 반환값integer
- 갇힌 물의 총 단위 수
제약 조건
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- 각 막대의 너비는 1단위이며, 물은 첫 번째 막대나 마지막 막대 너머에는 고이지 않습니다.
예제
- 입력
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- 출력
- 7
- 설명
- 3과 5 사이의 레벨은 3입니다. 1보다 2단위 위, 0보다 3단위 위, 2보다 1단위 위입니다. 뒤에 나오는 1은 5와 2 사이에 있으므로 1을 차지합니다. 그러면 7이 됩니다.
- 입력
- height = [4, 1, 3, 0, 5]
- 출력
- 8
- 설명
- 낮은 벽은 4이므로 물웅덩이는 높이 4까지 채워집니다. 1 위에 3단위, 3 위에 1단위, 0 위에 4단위로 총 8입니다. 5가 영향을 미치기 전에 물이 4를 넘어 흘러넘칩니다.
- 입력
- height = [1, 2, 4, 2, 1]
- 출력
- 0
- 설명
- 막대들은 4까지 올라갔다가 다시 내려갑니다. 모든 막대의 한쪽에는 그보다 더 높은 것이 없으므로 물이 흘러내리고 답은 0입니다.
후속 질문
막대가 높이로 이루어진 2D 격자를 형성하고 물이 네 방향 모두로 빠져나갈 수 있다고 가정해 봅시다. 그렇다면 갇힌 물의 양을 어떻게 계산할까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
행 전체는 잊고 막대 하나만 살펴보세요. 막대
i위로 물이 얼마나 높이 차오를 수 있으며, 그 높이는 어떤 막대들이 결정할까요?i막대 위의 물 높이는 두 수 중 더 작은 값입니다. 하나는 시작부터i까지 가장 높은 막대의 높이이고, 다른 하나는i부터 끝까지 가장 높은 막대의 높이입니다.i막대에는 그 높이에서 막대 자체의 높이를 뺀 만큼의 물이 고입니다. 양쪽 끝에서 각각 한 번씩 순회하면 두 누적 최댓값을 모두 구할 수 있습니다.두 최댓값 중 더 작은 값만 필요합니다. 양쪽 끝에 포인터를 하나씩 두고, 각 포인터가 지나온 막대 중 가장 높은 막대를 계속 기록합니다. 더 낮은 막대에 서 있는 포인터의 수위는 그 포인터가 기록한 현재 최댓값으로 결정됩니다. 그만큼의 물을 더하고 해당 포인터를 안쪽으로 이동합니다. 포인터가 만날 때 멈춥니다.
풀이
막대 위에 고이는 물의 양은 양쪽으로 멀리 떨어진 막대에 따라 달라질 수 있습니다. 수위는 왼쪽에서 가장 높은 막대와 오른쪽에서 가장 높은 막대 중 더 낮은 쪽이며, 막대 위에 고이는 물의 양은 그 수위에서 막대 자체의 높이를 뺀 값입니다. 두 접근 방식의 차이는 이 두 최댓값을 찾는 방법뿐입니다.
각 막대의 양쪽을 모두 스캔하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
각 막대 i에 대해 0부터 i까지 왼쪽에서 가장 높은 막대를 찾고, i부터 끝까지 오른쪽에서 가장 높은 막대를 찾은 다음 min(leftMax, rightMax) - height[i]를 더합니다. 두 탐색에 막대 i를 모두 포함하면 양이 음수가 되지 않으며 양 끝 막대의 값은 0이 됩니다.
모든 막대가 행 전체를 읽습니다. n = 2 × 10^4이면 4 × 10^8번 읽게 되며, 대부분은 바로 앞 막대의 탐색을 반복합니다.
알고리즘
water를 0으로 설정합니다.- 각 인덱스
i에 대해,leftMax를 찾기 위해 0부터i까지 탐색합니다. rightMax를 찾기 위해i부터 마지막 인덱스까지 탐색합니다.min(leftMax, rightMax) - height[i]를water에 더합니다.water를 반환합니다.
def trap(height):
n = len(height)
water = 0
for i in range(n):
# The tallest bar at or left of i, and the tallest at or right of i.
left_max = 0
for j in range(i + 1):
left_max = max(left_max, height[j])
right_max = 0
for j in range(i, n):
right_max = max(right_max, height[j])
water += min(left_max, right_max) - height[i]
return water각 측면에서 가장 높은 막대를 미리 계산합니다
핵심 아이디어
0부터 i까지의 가장 높은 막대는 0부터 i-1까지의 가장 높은 막대와 height[i] 중 더 큰 값입니다. 따라서 왼쪽에서 한 번 순회하면 leftMax가 채워지며, 각 항목은 바로 앞 항목을 바탕으로 계산됩니다. 오른쪽에서 한 번 순회하면 rightMax가 채워집니다. 세 번째 순회에서는 공식을 적용합니다.
[0, 3, 1, 0, 2, 5, 1, 2]에서 각 위치의 min(leftMax[i], rightMax[i]) 값은 [0, 3, 3, 3, 3, 5, 2, 2]입니다. 여기서 높이를 빼면 [0, 0, 2, 3, 1, 0, 1, 0]이 되고, 이 값들의 합은 7입니다. 시간 복잡도는 O(n)이며, 그 대가로 n개의 숫자로 이루어진 배열 두 개가 필요합니다.
알고리즘
leftMax를 왼쪽에서 오른쪽으로 채웁니다:leftMax[0] = height[0]로 설정한 다음leftMax[i] = max(leftMax[i-1], height[i])를 계산합니다.rightMax를 오른쪽에서 왼쪽으로 채웁니다:rightMax[n-1] = height[n-1]로 설정한 다음rightMax[i] = max(rightMax[i+1], height[i])를 계산합니다.- 모든 인덱스에 대해
min(leftMax[i], rightMax[i]) - height[i]를 합계에 더합니다. - 합계를 반환합니다.
def trap(height):
n = len(height)
left_max = [0] * n # tallest bar from index 0 to i
right_max = [0] * n # tallest bar from index i to n-1
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return water낮은 쪽으로 이동하는 두 포인터
핵심 아이디어
이 공식에는 더 낮은 벽만 필요하며, 두 개의 포인터로 어느 벽인지 증명할 수 있습니다. left를 0에서 시작하고 right를 마지막 인덱스에서 시작한 뒤, 각 포인터가 자기 위치를 포함해 지나온 막대 중 가장 높은 막대인 leftMax와 rightMax를 추적하고, 항상 더 낮은 막대 쪽 포인터를 이동합니다. 그러면 이미 지나온 모든 막대는 현재 두 막대 중 더 높은 막대보다 높지 않습니다. 포인터는 다른 포인터 아래에 있는 막대보다 높지 않은 막대만 지나가기 때문입니다.
height[left] < height[right]라고 해 봅시다. 불변식에 따라 leftMax는 left의 오른쪽에 있는 막대인 height[right]보다 높지 않습니다. 따라서 left의 오른쪽 벽은 적어도 leftMax만큼 높고, 두 포인터 사이에 무엇이 있든 그 수위는 정확히 leftMax입니다. 오른쪽 막대가 더 낮거나 같은 경우에는 대칭적인 논리로 right를 처리하면 됩니다.
알고리즘
left = 0,right = n-1로 설정하고leftMax,rightMax,water를 0으로 설정합니다.left < right인 동안 다음을 수행합니다.height[left] < height[right]이면 필요한 경우leftMax를height[left]로 올리고,leftMax - height[left]를 더한 다음left를 오른쪽으로 이동합니다.- 그렇지 않으면 오른쪽에서도 같은 작업을 수행하고
right를 왼쪽으로 이동합니다. water를 반환합니다. 포인터가 만나는 막대는 가장 높으므로 물을 담지 않습니다.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0 # tallest bar passed so far from each end
water = 0
while left < right:
if height[left] < height[right]:
# A bar taller than height[left] waits on the right, so left_max sets the level here.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# A bar at least as tall as height[right] waits on the left, so right_max sets the level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
함정과 경계 사례
- 누적 최댓값을 갱신하기 전에 물의 양을 더하는 경우.
height[left]가leftMax보다 크면 물의 양이 음수가 되어 총량이 줄어듭니다. - 수위가 보장되지 않은 더 높은 막대 쪽으로 포인터를 이동하는 경우.
[4, 1, 3, 0, 5]에서는 이 방식으로 정답 8 대신 4를 반환합니다. - 가장 가까운 이웃만 살펴보는 경우.
[3, 0, 2, 0, 1, 0, 4]에서 높이가 1인 막대는 네 칸과 두 칸 떨어진 막대가 정한 높이 3까지 물을 채우며, 정답은 12입니다. - 배열의 양 끝을 벽으로 취급하는 경우. 물은 양 끝으로 흘러나가므로 막대가 하나이거나 두 개이거나, 한 방향으로만 높아지거나 낮아지는 줄에는 물이 0만큼 담깁니다.
자주 묻는 질문3
빗물 담기의 시간 복잡도는 얼마인가요?
투 포인터 솔루션은 각 단계에서 포인터 하나를 안쪽으로 이동하므로 O(n) 시간과 O(1) 추가 공간을 사용합니다. leftMax 및 rightMax 배열 버전도 O(n) 시간이지만 O(n) 공간을 사용합니다. 각 막대에서 양쪽을 모두 스캔하면 O(n²)입니다.
스택으로 빗물 담기 문제를 풀 수 있을까요?
네. 높이가 낮아지는 인덱스들을 스택에 유지하세요. 더 높은 막대가 오면 맨 위를 꺼내세요. 이 막대는 새로 들어온 막대와 현재 막대로 둘러싸인 웅덩이의 바닥입니다. (min(two walls) - floor) × (distance between the walls - 1)를 더하고 계속 꺼내세요. 이렇게 하면 물을 수평 층으로 채우며, 시간과 공간 복잡도는 O(n)입니다.
Trapping Rain Water는 Container With Most Water와 어떻게 다른가요?
가장 많은 물을 담는 컨테이너 문제에서는 선이 공간을 차지하지 않으며, 정답은 두 선 사이의 가장 큰 직사각형 하나입니다. 여기서는 모든 막대가 꽉 차 있고, 정답은 모든 막대에 걸친 물의 양을 합한 값입니다. 두 경우 모두 같은 이유로 더 낮은 쪽을 이동합니다. 그쪽의 결과는 이미 결정되어 있기 때문입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def trap(height):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
height = [0, 3, 1, 0, 2, 5, 1, 2]
예상 출력
7