문제 · 알고리즘 보통 Python ·

Trapping rain water

The list gives the heights of bars of width 1 standing side by side. After rain, water collects between the bars. Return the total units of trapped water. Up to 500,000 bars.

함수 시그니처

def trap(heights: list[int]) -> int:

예제

trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])  # -> 6
trap([4, 2, 0, 3, 2, 5])  # -> 9

제한 시간이 적용되는 7 개의 비공개 테스트와 1 개의 대규모 입력 테스트가 추가로 진행되며, 입력값은 공개되지 않습니다. 문제는 모델에 영어로 주어집니다.

1위SpaceXAI Grok Build 0.1해결 · 테스트 10/10 통과응답 소요 8.7 초 · 실행 시간 201 ms · $0.0032

✓	trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])기댓값 6	<1 ms
✓	trap([4, 2, 0, 3, 2, 5])기댓값 9	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 194 ms

코드

def trap(heights: list[int]) -> int:
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    left_max = right_max = 0
    res = 0
    while left < right:
        if heights[left] < heights[right]:
            if heights[left] >= left_max:
                left_max = heights[left]
            else:
                res += left_max - heights[left]
            left += 1
        else:
            if heights[right] >= right_max:
                right_max = heights[right]
            else:
                res += right_max - heights[right]
            right -= 1
    return res

1위Qwen3.8 Max (0902)해결 · 테스트 10/10 통과응답 소요 7.1 초 · 실행 시간 217 ms · $0.0025

✓	trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])기댓값 6	3 ms
✓	trap([4, 2, 0, 3, 2, 5])기댓값 9	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 209 ms

코드

def trap(heights: list[int]) -> int:
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if heights[left] < heights[right]:
            if heights[left] >= left_max:
                left_max = heights[left]
            else:
                water += left_max - heights[left]
            left += 1
        else:
            if heights[right] >= right_max:
                right_max = heights[right]
            else:
                water += right_max - heights[right]
            right -= 1
    return water

1위MoonshotAI Kimi K2.7 Code해결 · 테스트 10/10 통과응답 소요 6.7 초 · 실행 시간 220 ms · $0.0012

✓	trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])기댓값 6	<1 ms
✓	trap([4, 2, 0, 3, 2, 5])기댓값 9	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 214 ms

코드

def trap(heights: list[int]) -> int:
    left, right = 0, len(heights) - 1
    left_max, right_max = 0, 0
    water = 0
    while left < right:
        if heights[left] < heights[right]:
            if heights[left] >= left_max:
                left_max = heights[left]
            else:
                water += left_max - heights[left]
            left += 1
        else:
            if heights[right] >= right_max:
                right_max = heights[right]
            else:
                water += right_max - heights[right]
            right -= 1
    return water

1위Google Gemini 4 Argon해결 · 테스트 10/10 통과응답 소요 16 초 · 실행 시간 236 ms · $0.0017

✓	trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])기댓값 6	<1 ms
✓	trap([4, 2, 0, 3, 2, 5])기댓값 9	<1 ms

✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 2 ms✓ 3 ms⏱ 224 ms

코드

from itertools import accumulate


def trap(heights: list[int]) -> int:
    if len(heights) < 3:
        return 0
    max_h = max(heights)
    idx = heights.index(max_h)
    return (
        sum(accumulate(heights[:idx], max))
        + sum(accumulate(heights[:idx:-1], max))
        - sum(heights)
        + max_h
    )

토큰 비용: $0.0086 · 진행 방식 및 점수 산정 안내 →