빗물 가두기(Trapping Rain Water) 문제란?
n개의 음수가 아닌 정수로 이루어진 배열이 있다고 가정해 봅시다. 이 배열은 각 막대의 너비가 1인 고도 지도(elevation map)를 나타내며, 비가 내린 후 이 지형에 얼마나 많은 물을 가둘 수 있는지 계산하는 것이 목표입니다. 예를 들어 다음과 같은 지형이 있다고 할 때 −
위 그림에서 파란색으로 표시된 물웅덩이가 총 6칸이므로, 결과값은 6이 됩니다.
이 문제는 각 위치에서 왼쪽과 오른쪽 경계 중 더 낮은 높이만큼 물이 차오른다는 원리를 이용하며, 스택(stack) 자료구조를 활용하면 한 번의 순회로 효율적으로 해결할 수 있습니다.
알고리즘 단계
스택 st와 water := 0, i := 0으로 초기화합니다.
i가 height 배열의 길이보다 작은 동안 아래 과정을 반복합니다.
스택이 비어 있거나 height[스택 최상단 값] >= height[i]라면, 현재 인덱스 i를 스택에 push하고 i를 1 증가시킵니다.
그렇지 않다면(현재 높이가 스택 top보다 높아 웅덩이가 생길 수 있는 경우):
x := 스택 top 요소를 꺼내고(pop) 저장합니다.
스택이 비어 있지 않다면:
temp := min(height[스택 top], height[i]) — 좌우 경계 중 낮은 값
dist := i – 스택 top – 1 — 두 경계 사이의 거리
water := water + dist × (temp – height[x]) — 해당 구간에 채워지는 물의 양을 누적
반복이 끝나면 누적된 water 값을 반환합니다.
예시 코드
다음 파이썬 구현을 통해 더 쉽게 이해할 수 있습니다 −
class Solution(object):
def trap(self, height):
stack = []
water = 0
i = 0
while i < len(height):
if len(stack) == 0 or height[stack[-1]] >= height[i]:
stack.append(i)
i += 1
else:
x = stack[-1]
stack.pop()
if len(stack) != 0:
temp = min(height[stack[-1]], height[i])
dist = i - stack[-1] - 1
water += dist * (temp - height[x])
return water
ob = Solution()
print(ob.trap([0,1,0,2,1,0,1,3,2,1,2,1]))
입력
[0,1,0,2,1,0,1,3,2,1,2,1]
출력
6
시간 및 공간 복잡도
각 인덱스는 스택에 최대 한 번 push되고 한 번 pop되므로 시간 복잡도는 O(n)입니다. 스택에는 인덱스가 저장되므로 공간 복잡도 역시 최악의 경우 O(n)입니다.