빗물 받기: 스택과 투 포인터
수평 층을 계산하는 단조 스택 방식과 수직 기둥을 계산하는 투 포인터 방식을 모두 사용해 빗물 받기 문제를 해결합니다.
빗물 받기: 스택과 투 포인터은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
문제: 빗물 가두기
빗물 가두기(LeetCode 42)는 가장 유명한 면접 문제 중 하나입니다. 각 막대의 너비가 1인 고도 지도를 나타내는 n개의 음이 아닌 정수가 주어질 때, 비가 온 뒤 막대 사이에 고일 수 있는 물의 양을 계산하세요. 양쪽에 더 높은 막대가 있는 골짜기에 물이 고입니다.
각 위치 i에서 물의 높이는 min(max_left[i], max_right[i]) - height[i]입니다. 이 값이 음수라면 물이 고이지 않습니다(막대가 양쪽 경계 중 하나보다 높기 때문입니다). 세 가지 방식이 있습니다. 미리 계산한 배열은 O(n)/O(n), 투 포인터는 O(n)/O(1), 단조 스택은 O(n)/O(n)입니다.
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
# Water trapped at each position:
# pos 2: min(1,3)-0=1
# pos 4: min(2,3)-1=1
# pos 5: min(2,3)-0=2
# pos 6: min(2,3)-1=1
# pos 9: min(3,2)-1=1
# Total = 6
print('height:', height)
print('Expected trapped water: 6')
# Visualise
max_h = max(height)
for row in range(max_h, 0, -1):
line = ''
for h in height:
line += '#' if h >= row else ' '
print(line)접근법 1: 미리 계산한 최댓값 배열
간단한 O(n) 시간, O(n) 공간 해법은 두 배열을 미리 계산합니다. max_left[i]는 인덱스 0부터 i까지의 최대 높이이고, max_right[i]는 인덱스 i부터 n-1까지의 최대 높이입니다. 위치 i에 고이는 물은 max(0, min(max_left[i], max_right[i]) - height[i])입니다.
max_left를 만들려면 왼쪽에서 오른쪽으로 한 번 순회해야 하고, max_right를 만들려면 오른쪽에서 왼쪽으로 순회해야 합니다. 마지막 순회에서 물의 양을 모두 더합니다. 이 방식은 깔끔하고 설명하기 쉽지만 O(n)의 추가 공간을 사용합니다.
def trap_prefix(height):
n = len(height)
if n < 3:
return 0
max_left = [0] * n
max_right = [0] * n
max_left[0] = height[0]
for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])
max_right[-1] = height[-1]
for i in range(n-2, -1, -1):
max_right[i] = max(max_right[i+1], height[i])
water = 0
for i in range(n):
water += max(0, min(max_left[i], max_right[i]) - height[i])
return water
print(trap_prefix([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_prefix([4,2,0,3,2,5])) # 9접근법 2: 투 포인터(O(1) 공간)
투 포인터 방식은 O(n) 시간과 O(1) 공간을 달성합니다. 양 끝에서 시작하는 왼쪽 포인터와 오른쪽 포인터를 사용하세요. 각 방향에서 지금까지 본 최댓값인 max_left와 max_right를 유지합니다.
각 단계에서는 지금까지의 최댓값이 더 작은 쪽을 처리합니다. 그쪽이 물의 높이를 제한하는 요소이기 때문입니다. max_left < max_right이면 왼쪽 포인터 위치의 물은 max_left - height[left]입니다(오른쪽이 충분히 높기 때문입니다). 왼쪽 포인터를 안쪽으로 이동하세요. 그렇지 않으면 대칭적으로 오른쪽을 처리합니다. 미리 계산한 배열은 필요하지 않습니다.
def trap_two_pointer(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left] # new max on the left
else:
water += max_left - height[left] # trapped by max_left
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap_two_pointer([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_two_pointer([4,2,0,3,2,5])) # 9
print(trap_two_pointer([3,0,3])) # 3투 포인터가 작동하는 이유: 불변식
핵심 아이디어는 다음과 같습니다. height[left] < height[right]이므로 왼쪽 포인터를 처리할 때 max_right >= height[right] > height[left]임을 알 수 있습니다. 따라서 오른쪽의 실질적인 물 경계는 적어도 height[right]이고, 이는 이미 max_left보다 큽니다. 그러므로 min(max_left, effective_max_right) = max_left가 되어 물의 공식이 max_left - height[left]로 단순해집니다.
정확한 max_right를 알 필요는 없습니다. height[right] > height[left]인 값 이상이라는 사실만 알면 max_left를 물의 높이로 사용하기에 충분합니다. 이것이 O(1) 공간을 가능하게 하는 우아한 불변식입니다.
# Trace two-pointer on [4, 2, 0, 3, 2, 5]
height = [4, 2, 0, 3, 2, 5]
left, right = 0, len(height) - 1
max_l = max_r = water = 0
print('height:', height)
print(f'{'Step':5} {'L':3} {'R':3} {'maxL':5} {'maxR':5} {'water':6} {'total':6}')
step = 0
while left < right:
side = 'L' if height[left] < height[right] else 'R'
if side == 'L':
if height[left] >= max_l: max_l = height[left]
else:
w = max_l - height[left]; water += w
left += 1
else:
if height[right] >= max_r: max_r = height[right]
else:
w = max_r - height[right]; water += w
right -= 1
step += 1
print(f'{step:5} {left:3} {right:3} {max_l:5} {max_r:5} {water:6}')
print('Total trapped:', water)접근법 3: 단조 스택(수평 레이어)
단조 스택 접근법은 인접한 막대 사이의 수평 레이어에 담기는 물을 계산합니다. 인덱스로 이루어진 단조 감소 스택을 유지합니다. 막대 i가 스택 맨 위의 j보다 높으면 골짜기가 형성됩니다. 이때 바닥은 height[j]이고, j를 제거한 후 왼쪽 벽은 height[stack[-1]]이며 오른쪽 벽은 height[i]입니다. 물은 min(left_wall, right_wall) - floor만큼의 높이까지 골짜기를 채우고, 너비는 i - stack[-1] - 1입니다.
더 높은 막대를 만날 때마다 각 ‘골짜기’를 계산합니다. 이 방식은 경계가 정해진 직사각형 영역 단위로 물을 처리하므로, 수위에 어떤 막대가 기여하는지도 추적해야 할 때 유용합니다.
def trap_stack(height):
stack = [] # monotonic decreasing indices
water = 0
for i in range(len(height)):
while stack and height[stack[-1]] < height[i]:
bottom_idx = stack.pop() # the floor of the valley
if not stack:
break # no left wall, no water
left_idx = stack[-1]
floor = height[bottom_idx]
water_height = min(height[left_idx], height[i]) - floor
width = i - left_idx - 1
water += water_height * width
stack.append(i)
return water
print(trap_stack([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_stack([4,2,0,3,2,5])) # 9단조 스택 추적
스택 접근법으로 [0,1,0,2,1,0,1,3,...]을 추적해 보겠습니다. 인덱스 3에서 막대 3(h=2)을 만났을 때 스택 맨 위는 i=2(h=0)이므로 이를 제거합니다. 왼쪽 벽은 i=1(h=1)이고 오른쪽 벽의 높이는 h=2입니다. 물의 높이 = min(1,2)-0=1, 너비=3-1-1=1, 면적=1입니다. 계속해서 스택 맨 위의 i=1(h=1)은 2보다 작지 않으므로 중단합니다. 그런 다음 3을 스택에 추가합니다.
스택 방식은 투 포인터보다 구현이 복잡하지만, 각 물 칸을 형성하는 구체적인 막대가 무엇인지 보여 줍니다. 이 통찰은 물이 배치된 모습을 재구성하거나 서로 다른 골짜기의 개수를 세는 후속 질문에서 유용합니다.
def trap_stack_trace(height):
stack = []
water = 0
for i in range(len(height)):
print(f'i={i} h={height[i]}: stack={[height[s] for s in stack]}')
while stack and height[stack[-1]] < height[i]:
bot = stack.pop()
if not stack:
print(f' Pop {height[bot]}: no left wall, skip')
break
left = stack[-1]
h = min(height[left], height[i]) - height[bot]
w = i - left - 1
water += h * w
print(f' Pop {height[bot]}: floor={height[bot]}, left_wall={height[left]}, right_wall={height[i]}, h={h}, w={w}, +{h*w}')
stack.append(i)
return water
result = trap_stack_trace([0,1,0,2,1,0,1,3,2,1,2,1])
print('Total:', result)세 가지 접근법 비교
빗물 가두기 문제를 해결하는 세 가지 접근법을 요약하면 다음과 같습니다.
- 접두사 배열: O(n) 시간, O(n) 공간. 이해하고 검증하기 가장 쉽습니다. 공간 효율성보다 명확성이 중요한 면접에 가장 적합합니다.
- 투 포인터: O(n) 시간, O(1) 공간. 시간과 공간 모두 최적입니다. ‘O(1) 공간으로 할 수 있나요?’라는 후속 질문에 가장 적합합니다.
- 단조 스택: O(n) 시간, O(n) 공간. 수평 레이어 단위로 물을 처리합니다. 어떤 막대가 기여하는지 알아야 하거나, 이 문제가 더 큰 스택 기반 알고리즘의 하위 문제로 등장할 때 가장 적합합니다.
height = [0,1,0,2,1,0,1,3,2,1,2,1]
# All three methods — verify they agree
def trap_prefix(h):
n = len(h)
ml = [0]*n; mr = [0]*n; ml[0]=h[0]; mr[-1]=h[-1]
for i in range(1,n): ml[i]=max(ml[i-1],h[i])
for i in range(n-2,-1,-1): mr[i]=max(mr[i+1],h[i])
return sum(max(0,min(ml[i],mr[i])-h[i]) for i in range(n))
def trap_two_ptr(h):
l,r,ml,mr,w = 0,len(h)-1,0,0,0
while l<r:
if h[l]<h[r]:
ml=max(ml,h[l]); w+=ml-h[l]; l+=1
else:
mr=max(mr,h[r]); w+=mr-h[r]; r-=1
return w
def trap_stk(h):
stk,w = [],[]
for i in range(len(h)):
while stk and h[stk[-1]]<h[i]:
b=stk.pop()
if not stk: break
w.append(max(0,min(h[stk[-1]],h[i])-h[b])*(i-stk[-1]-1))
stk.append(i)
return sum(w)
for h in [height, [4,2,0,3,2,5], [3,0,3], [1,0,1]]:
p=trap_prefix(h); t=trap_two_ptr(h); s=trap_stk(h)
print(f'{h}: prefix={p}, two-ptr={t}, stack={s}, match={p==t==s}')물을 가장 많이 담는 컨테이너
물을 가장 많이 담는 컨테이너(LeetCode 11)는 빗물 가두기 문제와 자주 혼동됩니다. 여기서는 정확히 두 개의 막대를 선택하며, 물은 그 두 막대에 의해서만 제한됩니다(내부 막대는 고려하지 않습니다). 넓이 min(height[l], height[r]) × (r - l)를 최대화하십시오.
투 포인터로 탐욕적으로 해결할 수 있습니다. 양 끝에서 시작하면 너비가 최대입니다. 더 짧은 막대 쪽 포인터를 안쪽으로 이동합니다. 더 높은 막대 쪽 포인터를 움직이면 넓이는 줄어들 수밖에 없습니다. 실행 시간은 O(n), 공간은 O(1)이며, 누적 최댓값이 필요하지 않으므로 빗물 가두기의 투 포인터 방식보다 간단합니다.
def max_water_container(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
# Move the shorter bar: moving taller bar can only reduce min
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
print(max_water_container([1,8,6,2,5,4,8,3,7])) # 49: bars 8 and 7
print(max_water_container([1,1])) # 1
print(max_water_container([4,3,2,1,4])) # 16
# Key difference from trapping rain water:
# Container: choose 2 bars, water fills freely between them (no internal barriers)
# Trapping: water fills ALL valleys in the full elevation map고급: 빗물 가두기 II (3D)
빗물 가두기 II(LeetCode 407)는 2차원 높이 행렬로 확장한 문제입니다. 물은 네 방향 모두로 흐를 수 있으며 경계를 넘어 빠져나가야 합니다. 해법은 최소 힙을 사용합니다. 먼저 모든 경계 셀을 힙에 넣은 다음 BFS와 유사하게 확장합니다. 높이가 가장 낮은 셀을 처리하면, 그보다 낮은 이웃 셀은 현재 셀의 높이만큼 물을 담을 수 있습니다.
이는 1차원 경우와 근본적으로 다른 알고리즘이며, 힙 연산과 BFS 순회를 모두 확인합니다. 1차원의 투 포인터 요령은 2차원으로 일반화되지 않지만, 힙 접근법은 일반화됩니다.
import heapq
def trap_rain_water_2d(heightMap):
if not heightMap or not heightMap[0]:
return 0
m, n = len(heightMap), len(heightMap[0])
visited = [[False]*n for _ in range(m)]
heap = [] # (height, row, col)
# Add all border cells to the heap
for i in range(m):
for j in [0, n-1]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
for j in range(n):
for i in [0, m-1]:
if not visited[i][j]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
total = 0
max_h = 0
while heap:
h, r, c = heapq.heappop(heap)
max_h = max(max_h, h)
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and not visited[nr][nc]:
visited[nr][nc] = True
total += max(0, max_h - heightMap[nr][nc])
heapq.heappush(heap, (max(max_h, heightMap[nr][nc]), nr, nc))
return total
map2d = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
print(trap_rain_water_2d(map2d)) # 4면접에서 각 방법을 사용하는 경우
빗물 가두기 면접 문제를 위한 선택 가이드입니다.
- 처음에는: 접두사 배열 — 설명하기 쉽고 시각적으로 직관적이며 올바름을 명확히 보여 줄 수 있습니다.
- ‘O(1) 공간으로 할 수 있나요?’라는 후속 질문에는: 투 포인터 — 더 작은 쪽이 병목이라는 불변 조건을 설명합니다.
- 면접관이 ‘다른 접근법은?’이라고 묻는다면: 단조 스택 — 수평 레이어 계산을 설명합니다.
코드로 넘어가기 전에 각 위치의 수위를 결정하는 요소, 즉 양쪽에서 가장 높은 막대 중 더 낮은 높이가 무엇인지 항상 명확히 정의하십시오. 이렇게 하면 문제를 제대로 이해하고 있음을 보여 주며 해법도 더 쉽게 설명할 수 있습니다.
# Quick summary of all three approaches
approaches = [
{
'name': 'Prefix max arrays',
'time': 'O(n)', 'space': 'O(n)',
'description': '3 passes: build max_left, max_right, sum water column-by-column',
},
{
'name': 'Two pointers',
'time': 'O(n)', 'space': 'O(1)',
'description': 'Process smaller side: its max is the limiting wall, no array needed',
},
{
'name': 'Monotonic stack',
'time': 'O(n)', 'space': 'O(n)',
'description': 'Compute water in horizontal layers when a taller bar is encountered',
},
]
for a in approaches:
print(f'{a["name"]} [{a["time"]} / {a["space"]}]')
print(f' {a["description"]}')
print()예외 상황과 흔한 실수
빗물 가두기 문제에서 흔히 하는 실수는 다음과 같습니다.
- min을 잊는 경우: 수위는
min(max_left, max_right)이며 둘 중 하나만 사용해서는 안 됩니다. 막대 양쪽 모두에 높은 벽이 있어야 합니다. - 음수인 물의 양: 어떤 위치의 높이가 수위보다 높을 때 음수 값이 0이 되도록
max(0, ...)을 사용해 제한합니다. - 가장자리 위치: 가장 왼쪽과 가장 오른쪽 막대는 한쪽에 벽이 없으므로 물을 담을 수 없습니다. 접두사 배열 접근법에서는
max_left[0] = height[0]이므로 인덱스 0의 물이 항상 0이 되어 이 경우를 자연스럽게 처리합니다. - 비어 있거나 매우 작은 배열: 원소가 3개보다 적은 배열에는 0을 반환합니다.
def trap(height):
n = len(height)
if n < 3:
return 0 # need at least 3 bars to trap anything
left, right = 0, n - 1
max_l = max_r = water = 0
while left < right:
if height[left] <= height[right]:
if height[left] >= max_l:
max_l = height[left]
else:
water += max_l - height[left] # never negative: max_l > height[left]
left += 1
else:
if height[right] >= max_r:
max_r = height[right]
else:
water += max_r - height[right]
right -= 1
return water
# Edge cases
print(trap([])) # 0: empty
print(trap([1])) # 0: single bar
print(trap([1,2])) # 0: two bars
print(trap([3,0,3])) # 3: simple valley
print(trap([3,3,3])) # 0: flat top, no water빠른 확인
이 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해를 확인해 보세요.
레슨 요약
이 레슨에서는 다음을 배웠습니다. 빗물 가두기는 각 위치에서 왼쪽과 오른쪽의 가장 높은 벽 중 더 낮은 높이를 찾는 문제입니다. 또한 더 작은 쪽의 누적 최댓값이 항상 결정적인 제약 조건이기 때문에 투 포인터 O(1) 공간 접근법이 작동합니다. 그리고 단조 스택 접근법은 물을 수평 레이어 단위로 계산하므로 다른 스택 기반 로직과 결합할 때 유용합니다. 다음으로는 구조화된 면접 답변을 위한 RADIO 프레임워크부터 시스템 설계 개념을 살펴보겠습니다.
자주 묻는 질문
“빗물 받기: 스택과 투 포인터” 강의는 무료인가요?
네 — “빗물 받기: 스택과 투 포인터” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“빗물 받기: 스택과 투 포인터”에서 뭘 배우나요?
수평 층을 계산하는 단조 스택 방식과 수직 기둥을 계산하는 투 포인터 방식을 모두 사용해 빗물 받기 문제를 해결합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“빗물 받기: 스택과 투 포인터” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 단조 스택: 증가형과 감소형
- 히스토그램에서 가장 큰 직사각형
- 단조 덱을 사용한 슬라이딩 윈도우 최댓값
- 빗물 받기: 스택과 투 포인터