Container With Most Water — 투 포인터 `O(n)`로 최대 넓이 한 번에 찾기

물을 가장 많이 담는 용기, 어떤 문제인가요?

LeetCode 11번 문제는 이렇게 주어집니다.

정수 배열 height가 주어집니다. i번째 선분의 양 끝점은 (i, 0)과 (i, height[i])입니다. 이 선분 두 개와 x축으로 만들 수 있는 컨테이너 중, 가장 많은 물을 담을 수 있는 경우의 넓이를 구해 반환하세요. 컨테이너를 기울일 수는 없습니다.

예시는 이렇습니다.

• height = [1, 8, 6, 2, 5, 4, 8, 3, 7] → 49
• height = [1, 1] → 1

제약은 다음과 같습니다.

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

핵심은 각 쌍의 넓이가 min(height[left], height[right]) * (right - left) 로 결정된다는 점입니다. 이 글에서는 모든 쌍을 다 보는 O(n²) 브루트포스부터, 왜 더 낮은 쪽 포인터만 움직이면 되는지까지 단계적으로 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

Phase 1. 브루트포스 — 모든 두 선분 쌍을 다 보기

가장 먼저 떠올릴 수 있는 방법은 모든 i < j 쌍에 대해 넓이를 직접 계산하는 것입니다.

fun maxArea(height: IntArray): Int {
    var answer = 0

    for (left in 0 until height.lastIndex) {
        for (right in left + 1..height.lastIndex) {
            val width = right - left
            val water = minOf(height[left], height[right]) * width
            answer = maxOf(answer, water)
        }
    }

    return answer
}

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]를 보면:

• (0, 1) → min(1, 8) * 1 = 1
• (1, 8) → min(8, 7) * 7 = 49
• (1, 6) → min(8, 8) * 5 = 40

이런 식으로 가능한 모든 쌍을 계산하면 정답은 구할 수 있습니다.

문제는 시간 복잡도입니다. 쌍의 수는 n * (n - 1) / 2개이므로 전체 시간은 O(n²)입니다. n = 10^5이면 대략 5 * 10^9쌍을 확인해야 하므로, 제한 시간 안에 끝나기 어렵습니다.

Phase 2. 투 포인터 — 양끝에서 시작해 더 낮은 쪽만 이동

브루트포스가 느린 이유는 "절대 최적이 될 수 없는 쌍"까지 전부 계산하기 때문입니다. 이 문제의 핵심은 현재 구간에서 더 낮은 선분이 넓이의 상한을 정한다는 점입니다.

그래서 양끝에서 시작합니다.

• left = 0
• right = n - 1
• 현재 넓이를 계산
• 더 낮은 쪽 포인터를 안쪽으로 한 칸 이동

코드는 이렇게 됩니다.

fun maxArea(height: IntArray): Int {
    var left = 0
    var right = height.lastIndex
    var answer = 0

    while (left < right) {
        val width = right - left
        val water = minOf(height[left], height[right]) * width
        answer = maxOf(answer, water)

        if (height[left] <= height[right]) {
            left++
        } else {
            right--
        }
    }

    return answer
}

같은 입력 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]를 따라가 보겠습니다.

left=0, right=8
넓이 = min(1, 7) * 8 = 8
→ 더 낮은 쪽은 1이므로 left++

left=1, right=8
넓이 = min(8, 7) * 7 = 49
→ answer = 49
→ 더 낮은 쪽은 7이므로 right--

left=1, right=7
넓이 = min(8, 3) * 6 = 18
→ right--

left=1, right=6
넓이 = min(8, 8) * 5 = 40
→ 같으면 한쪽만 움직여도 되므로 left++

이후에도 구간을 줄여 가며 계산하지만, 49보다 큰 넓이는 나오지 않습니다. 최종 정답은 49입니다.

시간 복잡도는 O(n)입니다. left와 right가 각각 한 방향으로만 움직이기 때문입니다. 추가 공간은 O(1)입니다.

Phase 3. 왜 더 낮은 쪽만 움직여야 하나요?

이 문제에서 가장 중요한 논리는 여기 있습니다.

현재 left, right에서 height[left] <= height[right]라고 가정하겠습니다. 이때 현재 넓이는:

current = height[left] * (right - left)

입니다. 이제 left는 그대로 두고 right만 줄이면 어떤 일이 생길까요?

• 폭 right - left는 반드시 줄어듭니다
• 높이는 min(height[left], height[newRight])인데, 이 값은 최대 height[left]입니다

즉 새 넓이의 상한은:

newArea <= height[left] * (newRight - left)
       <  height[left] * (right - left)
       =  current

입니다.

다시 말해, 더 낮은 쪽이 left라면 left를 고정한 채 right만 줄여서는 현재 넓이를 절대 이길 수 없습니다. 폭은 줄고, 높이 상한도 그대로이기 때문입니다.

그래서 현재 쌍을 계산한 뒤에는:

• 낮은 쪽을 버리고 더 높은 선분을 찾으러 가야 합니다
• 높은 쪽을 버리는 선택은 현재보다 더 좋아질 가능성이 없습니다

이 논리가 투 포인터의 정당성입니다.

높이가 같으면 어느 쪽을 움직여도 되나요?

됩니다. height[left] == height[right]라면 어느 쪽을 움직여도 폭은 줄어듭니다. 더 큰 넓이를 만들려면 결국 지금 높이보다 더 높은 선분을 만나야 하므로, 왼쪽을 움직이든 오른쪽을 움직이든 정답성에는 문제가 없습니다.

코드에서는 구현을 단순하게 유지하기 위해 height[left] <= height[right]일 때 left++를 선택했습니다.

참고: 같은 투 포인터라도 Is Subsequence는 한쪽 문자열을 끝까지 소비하는 스캔 패턴이고, 이 문제는 양끝 구간을 좁혀 가며 탐색 공간을 제거하는 패턴입니다. 둘 다 O(n)이지만, 포인터를 움직이는 근거는 다릅니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
[1, 1]	1	유일한 한 쌍의 넓이 1 * 1
[1, 2, 1]	2	양끝을 고르면 min(1, 1) * 2 = 2
[4, 3, 2, 1, 4]	16	가장 바깥 두 선분이 최대 넓이
[1, 2, 4, 3]	4	가장 높은 두 선분이 아니라 (1, 3)이 정답

마지막 예시가 중요합니다. 가장 높은 두 선분을 고르는 것이 정답은 아닙니다. 폭과 낮은 쪽 높이를 함께 봐야 합니다.

두 풀이를 다시 비교

풀이	시간	공간	특징
모든 쌍 브루트포스	O(n²)	O(1)	구현은 단순하지만 큰 입력에서 비현실적
투 포인터	O(n)	O(1)	양끝에서 시작해 낮은 쪽만 이동

마무리

1. 이 문제의 넓이는 min(왼쪽 높이, 오른쪽 높이) * 폭으로 결정됩니다 — 높은 선분 하나만 커도 충분하지 않고, 더 낮은 쪽이 실제 높이 상한이 됩니다
2. 투 포인터가 성립하는 이유는 "낮은 쪽을 고정한 채 반대쪽만 줄여서는 현재 넓이를 절대 이길 수 없기 때문" — 폭은 줄고, 높이 상한도 그대로입니다
3. 그래서 매 단계에서 더 낮은 쪽 포인터만 움직이면 됩니다 — 이 선택이 탐색 공간을 안전하게 제거해 O(n)을 만듭니다
4. 이 문제는 같은 투 포인터라도 "문자 매칭"이 아니라 "탐색 공간 제거" 패턴이라는 점이 핵심 — 포인터 이동의 이유를 식으로 설명할 수 있어야 제대로 이해한 것입니다