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 사이에 있으므로, 물의 높이는 2이고 1단위의 물이 고입니다. 2 + 3 + 1 + 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입니다.
제출 시 숨은 테스트 +17개
후속 질문
막대들이 높이로 이루어진 2D 격자를 형성하고 물이 네 방향 모두로 빠져나갈 수 있다고 가정해 보세요. 그렇다면 갇힌 물의 양을 어떻게 셀 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
행 전체는 잊고 막대 하나를 살펴보세요. 막대
i위로 물이 얼마나 높이 고일 수 있으며, 어떤 막대들이 그 높이를 결정할까요?i막대 위의 수위는 두 숫자 중 더 작은 값입니다. 시작부터i까지의 가장 높은 막대와i부터 끝까지의 가장 높은 막대입니다.i막대에는 그 수위에서 막대 자체의 높이를 뺀 만큼의 물이 고입니다. 양쪽 끝에서 각각 한 번씩 순회하면 두 누적 최댓값을 모두 구할 수 있습니다.두 최댓값 중 더 작은 값만 있으면 됩니다. 양쪽 끝에 포인터를 하나씩 두고 각 포인터가 지나온 가장 높은 막대를 계속 기록하세요. 더 낮은 막대에 서 있는 포인터는 자신의 현재 최댓값으로 수위가 결정됩니다. 그만큼 물을 더하고 해당 포인터를 안쪽으로 이동하세요. 포인터가 만날 때 멈추세요.
풀이
각 막대 위의 물은 양쪽에 멀리 떨어져 있는 막대들에 따라 달라지므로, 이웃 막대만 살펴보면 잘못 계산하게 됩니다. 해결 방법은 하나의 공식입니다. 막대 위의 수위는 왼쪽에서 가장 높은 막대와 오른쪽에서 가장 높은 막대 중 더 낮은 높이입니다. 각 막대에서 이 두 최댓값을 찾아가며 스캔하는 방법은 느리고, 두 배열에 저장하면 선형 시간이 걸리며, 더 낮은 쪽을 항상 이동하는 두 포인터를 사용하면 배열이 전혀 필요하지 않습니다.
모든 막대의 양쪽을 모두 살펴보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
물을 열마다 계산합니다. 막대 i 위의 물은 양쪽 벽 중 낮은 쪽을 넘어 흘러내리기 전까지 차오릅니다. 왼쪽 벽은 인덱스 0부터 i까지 어디서든 가장 높은 막대이고, 오른쪽 벽은 i부터 끝까지 가장 높은 막대입니다. 따라서 수위는 min(leftMax, rightMax)이고, 막대 i 위의 물의 양은 그 수위에서 height[i]를 뺀 값입니다.
[0, 3, 1, 0, 2, 5, 1, 2]에서 인덱스 3에 있는 높이 0인 막대를 살펴보겠습니다. 왼쪽에서 가장 높은 막대는 3이고, 오른쪽에서는 5입니다. 수위는 3이므로 그곳에는 물이 3단위 고입니다. 인덱스 6에 있는 높이 1인 막대의 경우 벽은 5와 2입니다. 수위는 2이고 물은 1단위 고입니다.
두 번의 탐색 모두 막대 i 자체를 포함합니다. 덕분에 결과가 음수가 되지 않습니다. 막대 i가 한쪽의 다른 모든 막대보다 높으면, 그쪽의 최댓값은 막대 자체의 높이가 되고 수위는 그 높이와 같아져 물은 0만큼 고입니다. 이것이 첫 번째와 마지막 막대에 항상 물이 0만큼 고이는 이유이기도 합니다.
문제는 비용입니다. 각 막대마다 행 전체를 읽고, 절반은 왼쪽에서 절반은 오른쪽에서 읽으므로 총 n × n번 읽게 됩니다. 막대가 2 × 10^4개라면 4 × 10^8번입니다. 또한 두 탐색은 서로 중복됩니다. 인덱스 5의 왼쪽에서 가장 높은 막대는 인덱스 4의 왼쪽에서 가장 높은 막대에 비교 한 번을 더하면 구할 수 있지만, 무차별 대입 방식은 매번 처음부터 다시 계산합니다.
알고리즘
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가 채워집니다. 세 번째 순회에서는 각 막대에 대해 min(leftMax[i], rightMax[i]) - height[i]를 더합니다.
[0, 3, 1, 0, 2, 5, 1, 2]의 경우 leftMax = [0, 3, 3, 3, 3, 5, 5, 5]이고 rightMax = [5, 5, 5, 5, 5, 5, 2, 2]입니다. 두 값 중 작은 값은 높이 [0, 3, 3, 3, 3, 5, 2, 2]가 됩니다. 여기서 막대 높이를 빼면 [0, 0, 2, 3, 1, 0, 1, 0]을 얻으며, 이 값들의 합은 7입니다.
각 순회는 모든 막대를 한 번씩 확인하므로 시간 복잡도는 O(n)입니다. 막대가 2 × 10^4개일 때 약 6 × 10^4번의 단계가 필요하며, 4 × 10^8번이 아닙니다. 대신 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는 height[right]보다 크지 않고, height[right] 자체도 left의 오른쪽에 있는 막대입니다. 따라서 left의 실제 오른쪽 벽은 leftMax 이상으로 높고, 두 포인터 사이에 무엇이 있든 left의 수위는 정확히 leftMax입니다. leftMax - height[left]를 더하고 left를 오른쪽으로 한 칸 이동합니다. height[right]가 더 낮거나 같은 막대일 때는 오른쪽에서도 같은 방식으로 처리합니다. 물을 더하기 전에 현재까지의 최댓값을 갱신하면 포인터 아래의 막대도 자신의 벽으로 계산되며 물의 양은 음수가 되지 않습니다.
[0, 3, 1, 0, 2, 5, 1, 2]를 따라가 봅시다. 포인터는 0과 2에서 시작합니다. 왼쪽이 더 낮으므로 0을 담습니다. 다음에는 3과 2를 비교합니다. 오른쪽이 더 낮고, rightMax는 2가 되며, 0을 담습니다. 그다음에는 3과 1을 비교합니다. 다시 오른쪽이 더 낮으므로 1은 2-1 = 1을 담습니다. 이어서 3과 5를 비교하면 왼쪽이 더 낮습니다. leftMax는 3이고, 3은 0을, 1은 2를, 0은 3을, 2는 1을 담습니다. 포인터는 5에서 만납니다. 한 번 순회하고 변수 네 개만 사용해 얻는 총합은 1 + 2 + 3 + 1 = 7입니다.
알고리즘
left = 0,right = n-1로 설정하고,leftMax,rightMax,water를 0으로 설정합니다.left < right인 동안height[left]와height[right]를 비교합니다.- 왼쪽 막대가 더 낮으면 필요한 경우
leftMax를height[left]로 높이고,leftMax - height[left]를 더한 다음left를 오른쪽으로 이동합니다. - 그렇지 않으면 필요한 경우
rightMax를height[right]로 높이고,rightMax - height[right]를 더한 다음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보다 크면leftMax - height[left]는 음수가 되어 총합이 줄어듭니다. 먼저 최댓값을 갱신한 다음 더하세요. - 더 높은 막대 쪽 포인터를 이동하는 경우. 수위는 더 낮은 쪽에서만 알 수 있습니다. 더 높은 쪽을 이동하면 아직 확인하지 않은 벽을 기준으로 삼게 됩니다.
[4, 1, 3, 0, 5]에서는 이 방식으로 8이 아니라 4를 반환합니다. - 바로 옆 이웃만 살펴보는 경우. 막대의 벽은 멀리 있을 수 있습니다.
[3, 0, 2, 0, 1, 0, 4]에서 1 높이의 막대는 네 칸, 두 칸 떨어진 막대가 정하는 수위 3까지 물을 담습니다. 이 경우 정답은 12입니다. - 배열의 양 끝을 벽으로 취급하는 경우. 첫 번째나 마지막 막대 너머로 물이 흘러나가므로 막대가 하나 또는 둘뿐이거나, 한 방향으로만 높아지거나 낮아지는 배열은 물을 0만큼 담습니다.
- 브루트 포스에서 막대
i를 자기 자신을 포함하는 탐색에서 제외하는 경우. 그러면 양쪽보다 높은 막대는 음수 양을 갖게 됩니다. 해당 막대를 포함하거나 결과를 0으로 제한하세요. - 곱셈을 사용하는 변형에서의 오버플로. 여기서 정답은 약 2 × 10^9 (10^5 높이의 막대 두 개 사이에 빈 칸 19,998개)까지 이르지만, 부호 있는 32비트 정수에 여전히 들어갑니다. 직접 변형을 구현할 때는 64비트 합계를 사용하세요.
자주 묻는 질문4
Trapping Rain Water의 시간 복잡도는 얼마인가요?
두 포인터 풀이는 O(n) 시간과 O(1) 추가 공간을 사용합니다. 각 단계에서 포인터 하나가 안쪽으로 이동하므로 단계 수는 n-1입니다. leftMax 및 rightMax 배열을 사용하는 방식도 O(n) 시간이 걸리지만 O(n) 공간을 사용합니다. 각 막대에서 양쪽을 모두 스캔하면 O(n²)이며, 막대가 2 × 10^4개일 때 약 4 × 10^8번 읽게 됩니다.
투 포인터 풀이에서 더 짧은 쪽을 이동해도 되는 이유는 무엇인가요?
이미 지나간 모든 막대의 높이는 현재 두 막대 중 더 높은 막대의 높이를 넘지 않습니다. 더 낮은 쪽 포인터만 움직이기 때문입니다. 따라서 왼쪽 막대가 더 낮을 때 왼쪽의 현재까지 최댓값은 오른쪽 막대의 높이보다 작거나 같고, 오른쪽 막대는 실제로 오른쪽을 막아 주는 벽입니다. 포인터 사이에 무엇이 있든 왼쪽 포인터의 수위는 왼쪽의 현재까지 최댓값이므로, 해당 막대의 처리를 마치고 다음으로 넘어갈 수 있습니다.
스택으로 빗물 트래핑 문제를 해결할 수 있을까요?
네. 높이가 아래에서 위로 갈수록 낮아지는 인덱스 스택을 유지하세요. 맨 위 항목보다 높은 막대가 나오면 맨 위 항목을 꺼냅니다. 이 항목은 스택의 새 맨 위 항목과 현재 막대가 양쪽 벽인 웅덩이의 바닥입니다. (min(two walls) - floor) × (distance between the walls - 1)를 더하고, 현재 막대가 더 높은 동안 계속 꺼냅니다. 이 스택은 물을 기둥이 아니라 수평 층으로 채우며, O(n) 시간과 O(n) 공간이 필요합니다.
Trapping Rain Water는 Container With Most Water와 어떻게 다른가요?
가장 많은 물을 담는 용기 문제에서는 두 개의 선을 고르고, 그 사이의 선들은 공간을 차지하지 않으므로 답은 가장 큰 직사각형 하나입니다. 여기서는 모든 막대가 꽉 차 있고, 각 막대 위에 물이 담기므로 답은 모든 막대의 합입니다. 두 경우 모두 같은 이유로 더 낮은 쪽을 움직이는 투 포인터를 사용합니다. 더 낮은 쪽은 이미 결과가 결정된 쪽이기 때문입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def trap(height):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
height = [0, 3, 1, 0, 2, 5, 1, 2]
기대값
7