기둥 사이에 고인 빗물

레벨 D8 · 코딩 · JavaScript · 목표 시간 8분 · 게시일 2026-10-10

폭이 1인 기둥들의 높이가 왼쪽부터 차례로 heights에 담겨 있다. 비가 충분히 내린 뒤 기둥 사이에 고이는 빗물의 총량을 반환하시오. 한 칸에 고이는 물의 높이는, 그 칸을 포함해 왼쪽에서 가장 높은 기둥과 그 칸을 포함해 오른쪽에서 가장 높은 기둥 중 낮은 쪽의 높이에서 그 칸의 높이를 뺀 값이다.

heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]  →  6

heights의 길이는 최대 200,000이고, 각 높이는 0 이상 100,000 이하이다. 칸마다 양쪽을 다시 훑는 방법으로는 시간 안에 끝나지 않는다.

예제

solve([0,1,0,2,1,0,1,3,2,1,2,1])
solve([4,2,0,3,2,5])
solve([])

D8 레벨의 다른 문제 · 코딩 문제 목록