LeetCode 11 - Container With Most Water

두 수직선 사이에 담을 수 있는 물의 최대 넓이를 구하는 Medium 문제다. 모든 쌍을 확인하면 간단하지만 시간 복잡도가 O(n²)이 되므로, 양 끝에서 시작하는 two pointers로 탐색 범위를 줄였다.

문제 링크 & 설명

문제 링크: 11. Container With Most Water
요약: 각 위치의 높이가 담긴 배열에서 두 선을 골라, 두 선과 x축이 만드는 용기의 최대 넓이를 구한다.

두 선의 거리는 가로 길이가 되고, 물의 높이는 둘 중 더 낮은 선을 넘을 수 없다. 따라서 left와 right를 골랐을 때 넓이는 (right - left) * min(height[left], height[right])로 계산한다.

접근 방법

left는 배열의 처음, right는 마지막에서 시작한다. 현재 넓이를 계산해 최댓값을 갱신한 다음 두 높이 중 더 낮은 쪽의 포인터를 안으로 옮긴다.

area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)

if height[left] < height[right]:
    left += 1
else:
    right -= 1

더 높은 쪽을 옮겨도 현재 넓이를 제한하는 낮은 높이는 그대로 남고 가로 길이만 줄어든다. 반면 낮은 쪽을 옮기면 가로 길이는 줄어들지만, 더 높은 선을 만나 물의 높이가 커질 가능성이 생긴다. 이 기준 덕분에 모든 조합을 만들지 않고도 한 번의 순회로 답을 찾을 수 있다.

복잡도 분석

시간 복잡도: O(n)
- 매 반복마다 left 또는 right가 한 칸 이동하므로 각 위치를 최대 한 번씩 확인한다.
공간 복잡도: O(1)
- 두 포인터와 최대 넓이를 저장하는 변수만 사용한다.

구현 코드

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1

        max_area = 0
        while left < right:
            area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, area)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

요약 및 회고

이 문제에서 two pointers를 움직이는 기준은 현재 넓이를 제한하는 쪽이 어디인지에 달려 있었다. 낮은 선을 남겨둔 채 가로 길이만 줄이는 선택은 더 큰 넓이를 만들 수 없으므로 바로 제외할 수 있다. 포인터 이동 규칙을 외우기보다, 어떤 값이 현재 결과의 상한을 정하는지 확인하는 편이 훨씬 이해하기 쉬웠다.