LeetCode

LeetCode 11 Container With Most Water 풀이: 짧은 쪽을 이동하는 투 포인터

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

모든 선의 쌍을 비교하면 최대 10^5개 선에서 O(n²) 시간이 걸려 제한을 넘는다. 짧은 선이 컨테이너 높이를 결정한다는 점을 이용해 포인터를 한쪽씩 옮기면 후보를 선형 시간에 줄일 수 있어 Level 3으로 판단했다.

1. 문제 요약

height[i]는 x축의 위치 i에 세워진 수직선의 높이다. 두 선과 x축이 만드는 컨테이너가 담을 수 있는 물의 최대량을 구한다.

두 선의 인덱스가 left, right일 때 컨테이너의 넓이는 다음과 같다.

물의 양 = min(height[left], height[right]) * (right - left)

컨테이너의 높이는 두 선 중 짧은 선을 넘을 수 없고, 너비는 두 인덱스 사이의 거리다. 높이 배열의 길이는 2 이상 10^5 이하이며, 높이는 0 이상 10^4 이하다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그리디 선택 기준

가장 넓은 컨테이너에서 시작하기 위해 left = 0, right = n - 1로 초기화한다. 현재 두 선으로 만들 수 있는 물의 양을 계산한 뒤, 두 선 중 더 짧은 쪽의 포인터를 안쪽으로 한 칸 이동한다.

  • height[left] <= height[right]이면 left를 증가시킨다.
  • 그렇지 않으면 right를 감소시킨다.

두 포인터가 만날 때까지 반복한다.

짧은 선을 옮겨도 최적해를 놓치지 않는 이유

현재 왼쪽 선이 짧다고 하자. 왼쪽 선을 고정한 채 오른쪽만 안쪽으로 옮기면 너비가 줄고, 높이는 계속 height[left] 이하로 제한된다. 따라서 이렇게 만드는 모든 컨테이너는 현재 넓이보다 작다. 이 왼쪽 선을 더는 후보로 볼 필요가 없으므로 left를 옮긴다. 오른쪽 선이 더 짧을 때도 같은 논리로 right를 옮긴다.

공식 예제의 첫 세 비교는 이동 규칙을 이렇게 보여준다.

left right 양끝 높이 넓이 다음 이동
0 8 1, 7 8 왼쪽 높이 1이 짧으므로 left += 1
1 8 8, 7 49 오른쪽 높이 7이 짧으므로 right -= 1
1 7 8, 3 18 오른쪽 높이 3이 짧으므로 right -= 1

첫 비교에서 왼쪽 선을 남기고 오른쪽을 더 옮겨도 높이는 1을 넘지 않고 너비만 감소한다. 따라서 짧은 쪽을 버리는 이동만이 더 높은 경계를 찾아 넓이를 회복할 가능성을 남긴다. 높이가 같다면 어느 한쪽을 옮겨도 같은 논리가 적용된다. 구현에서는 왼쪽을 이동한다.

시간·공간 복잡도

반복할 때마다 왼쪽 또는 오른쪽 포인터 하나가 반드시 이동하고, 각 포인터는 배열을 한 번만 통과한다. 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

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

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

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

        return best

현재 넓이를 계산한 후 더 짧은 선의 포인터를 이동한다. 높이가 같을 때는 왼쪽을 이동하지만, 오른쪽을 이동해도 최댓값을 놓치지 않는다. width는 선 사이의 간격이므로 right - left로 계산하며, 양끝 인덱스를 모두 포함하는 길이인 right - left + 1이 아니다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 공식 예제와 높이 경계를 확인할 수 있다.

solver = Solution()
assert solver.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert solver.maxArea([1, 1]) == 1
assert solver.maxArea([0, 0, 0]) == 0

4. 공식 예제와 추가 검증

공식 예제와 동일한 높이, 0 높이, 양끝이 아닌 내부의 높은 선을 포함한 케이스를 Python 코드로 실행했다.

공식 예제

입력 기대 출력 확인 결과
height = [1, 8, 6, 2, 5, 4, 8, 3, 7] 49 통과
height = [1, 1] 1 통과

추가 검증 1: 세 선의 양끝과 가운데

입력: height = [1, 2, 1]
기대 출력: 2
확인 결과: 통과
검증 목적: 짧은 양끝을 이동해 가운데 높이를 탐색하는지 확인

추가 검증 2: 모든 높이가 같은 경우

입력: height = [5, 5, 5]
기대 출력: 10
확인 결과: 통과
검증 목적: 같은 높이에서 한 포인터만 이동하는지 확인

추가 검증 3: 높이가 모두 0인 경우

입력: height = [0, 0, 0]
기대 출력: 0
확인 결과: 통과
검증 목적: 높이가 0인 컨테이너의 경계 처리 확인

추가 검증 4: 한쪽에 매우 높은 선이 있는 경우

입력: height = [1, 100, 2, 3, 4]
기대 출력: 12
확인 결과: 통과
검증 목적: 높은 선보다 반대쪽의 짧은 선이 넓이를 제한하는지 확인

5. 다른 풀이 방식 검색 및 비교

완전탐색은 모든 쌍을 확인해 직관적이지만 O(n^2) 시간이 필요하다. 양끝에서 시작해 짧은 선을 이동하는 투 포인터는 최적이 될 수 없는 쌍을 증명과 함께 버리므로 O(n)에 최댓값을 구한다. 높이가 같은 경우 한 포인터만 이동하는 것이 두 포인터를 모두 이동하는 것보다 안전하다.

마무리

Container With Most Water는 너비와 짧은 선의 높이가 함께 넓이를 결정한다는 점을 이용하는 그리디 투 포인터 문제다. 처음에는 가장 넓은 구간을 확인하고, 더 큰 넓이를 만들 가능성이 있는 짧은 선만 교체하면 모든 포인터 이동을 O(n) 안에 처리할 수 있다.

#투 포인터#LeetCode#난이도 3