파이썬으로 풀어보는 '물이 가장 많이 담기는 용기' 문제

음이 아닌 정수 n개(a₁, a₂, ..., aₙ)가 주어졌다고 가정해 보겠습니다. 각 값은 좌표 평면 위의 점 (i, a[i])을 나타내며, 이 점들을 통해 n개의 수직선이 만들어집니다. 여기서 i번째 수직선의 두 끝점은 각각 (i, a[i])와 (i, 0)입니다.

우리의 목표는 이 수직선들 중 두 개를 선택해 x축과 함께 하나의 '용기(컨테이너)'를 형성할 때, 담을 수 있는 물의 양이 최대가 되는 두 개의 기둥을 찾는 것입니다.

예를 들어 배열이 [1,8,6,2,5,4,8,3,7]이라면 다음 그림과 같이 표현할 수 있습니다.

위 그림에서 음영 처리된 영역을 살펴보면, 높이는 7이고 너비는 7칸입니다. 따라서 담을 수 있는 물의 총량(면적)은 7 × 7 = 49가 되며, 이것이 바로 우리가 구해야 하는 정답입니다.

해결 접근 방법

이 문제는 두 포인터(Two Pointer) 기법을 활용하면 O(n)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• low := 0, high := 배열 길이 - 1, ans := 0으로 초기화합니다.
• low < high인 동안 다음 과정을 반복합니다.
  • arr[low] < arr[high]라면, min_h := height[low], min_ind := low로 설정합니다.
  • 그렇지 않다면, min_h := height[high], min_ind := high로 설정합니다.
  • ans := max((high - low) × min_h, ans)로 현재까지의 최대 넓이를 갱신합니다.
  • 더 짧은 쪽의 기둥이 최소 높이에 해당하므로, 해당 포인터(low 또는 high)를 안쪽으로 한 칸 이동시킵니다.
• 반복이 끝나면 ans를 반환합니다.

예제 코드

아래 파이썬 구현 예제를 통해 더 자세히 이해해 보겠습니다.

class Solution(object):
    def maxArea(self, height):
        low = 0
        high = len(height) - 1
        ans = 0
        while low < high:
            if height[low] < height[high]:
                min_height = height[low]
                min_height_index = low
            else:
                min_height = height[high]
                min_height_index = high
            ans = max(((high - low)) * min_height, ans)
            if low + 1 == min_height_index + 1:
                low += 1
            else:
                high -= 1
        return ans

ob1 = Solution()
print(ob1.maxArea([1,8,6,2,5,4,8,3,7]))

입력

[1,8,6,2,5,4,8,3,7]

출력

49