← 전체 회차
A-014● Day 142026.05.16hardleetcode #42neetcode150

빗물 정거량

#array#two-pointers#dynamic-programming#stack#monotonic-stack
↗ leetcode #42 · trapping-rain-water
01

문제

· problem
P.014

빗물 정거량

↗ leetcode #42

n개의 음이 아닌 정수로 이루어진 배열이 주어지며, 이는 높이 맵을 나타냅니다. 여기서 각 막대의 너비는 1입니다. 비가 내린 후 얼마나 많은 물을 담을 수 있는지 계산하세요.

제약
  • · n == height.length
  • · 1 ≤ n ≤ 2 × 10⁴
  • · 0 ≤ height[i] ≤ 10⁵
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[0,1,0,2,1,0,1,3,2,1,2,1]
6
example 2input → output
[4,2,0,3,2,5]
9
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    각 위치에서 담을 수 있는 물의 양은 무엇에 의해 결정되나?
  • ☐
    왜 두 포인터 방식에서 leftMax < rightMax일 때 항상 왼쪽 포인터를 이동하나?
  • ☐
    이 알고리즘의 시간과 공간 복잡도는?
  • ☐
    배열을 정렬해서 이 문제를 풀 수 있을까?
  • ☐
    각 위치의 물의 높이는 height[i]와 같은가?
  • ☐
    동적 계획법으로 모든 위치의 leftMax와 rightMax를 미리 계산해야 하나?
  • ☐
    단조 스택으로도 이 문제를 풀 수 있을까?
  • ☐
    포인터가 만날 때까지 반복해야 하는 이유는?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 빈 배열 확인
○
if not height:
○
if len(height) == 0:
○
if height is None:
step 2· 양쪽 포인터 초기화
○
l, r = 0, len(height) - 1
○
l, r = 0, len(height)
○
l, r = 1, len(height) - 2
step 3· 양쪽 경계의 최대 높이 초기화
○
leftMax, rightMax = height[l], height[r]
○
leftMax, rightMax = 0, 0
○
leftMax, rightMax = height[0], height[len(height)-1]
step 4· 주 순회 루프
○
while l < r:
○
while l <= r:
○
for i in range(len(height)):
step 5· 좌측 경계 처리 (최대값 업데이트)│ 중첩
○
leftMax = max(leftMax, height[l])
○
leftMax = height[l]
○
leftMax = leftMax + height[l]
step 6· 좌측에서 물의 양 누적│ │ 중첩
○
res += leftMax - height[l]
○
res += height[l] - leftMax
○
res = leftMax - height[l]
step 7· 우측 경계 처리 (최대값 업데이트)│ 중첩
○
rightMax = max(rightMax, height[r])
○
rightMax = height[r]
○
rightMax = rightMax + height[r]
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def trap(self, height: List[int]) -> int:
3
        if not height:
4
            return 0
5
6
        l, r = 0, len(height) - 1
7
        leftMax, rightMax = height[l], height[r]
8
        res = 0
9
        while l < r:
10
            if leftMax < rightMax:
11
                l += 1
12
                leftMax = max(leftMax, height[l])
13
                res += leftMax - height[l]
14
            else:
15
                r -= 1
16
                rightMax = max(rightMax, height[r])
17
                res += rightMax - height[r]
18
        return res
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[0,1,0,2,1,0,1,3,2,1,2,1]
→
6
case 2
[4,2,0,3,2,5]
→
9
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.