[leetcode] Container With Most Water

문제

음이 아닌 n개의 정수 a1, a2, ..., an이 주어지면 각각은 좌표 (i, ai)의 점을 나타냅니다. 선 i의 두 끝 점이 (i, ai) 및 (i, 0)에 있도록 n 개의 수직선이 그려집니다. 컨테이너가 가장 많은 물을 포함하도록 X 축과 함께 컨테이너를 형성하는 두 개의 선을 찾습니다.

컨테이너는 기울일 수 없습니다.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 위의 수직선은 배열 [1,8,6,2,5,4,8,3,7]로 표시됩니다. 이 경우 용기에 담을 수있는 물의 최대 면적 (파란색 섹션)은 49입니다.

Example 2:

Input: height = [1,1]
Output: 1

Example 3:

Input: height = [4,3,2,1,4]
Output: 16

Example 4:

Input: height = [1,2,1]
Output: 2

제약 조건:

• n == height.length
• 2 <= n <= 3 * 104
• 0 <= height[i] <= 3 * 10^4

Hint #1  

목표는 수직선 사이에 형성된 면적을 최대화하는 것입니다. 컨테이너의 면적은 더 짧은 선을 길이로, 선 사이의 거리를 직사각형의 너비로 사용하여 계산됩니다.
면적 = (더 짧은 수직선의 길이 * 선 사이의 거리)
가장 바깥 쪽 선이 그들 사이에 최대 거리를 가지므로 최대 너비 컨테이너를 확실히 얻을 수 있습니다. 그러나 이 컨테이너의 수직선 중 하나가 정말 짧을 수 있으므로 이 컨테이너의 크기가 최대가 아닐 수 있습니다.

 

Hint #2  

최대 너비 컨테이너로 시작하고 현재 컨테이너 짧은 줄보다 세로줄이 더 긴 경우 더 짧은 너비 컨테이너로 이동합니다. 이런 식으로 우리는 너비를 타협하고 있지만 더 긴 길이의 컨테이너를 기대하고 있습니다.

풀이

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = [0, height[0]]
        right = [len(height)-1, height[-1]]
        area = 0
        
        while left[0] != right[0]:
            if left[1] < right[1]:
                shorter = left
                r = range(left[0]+1, right[0]+1)
            else:
                shorter = right
                r = range(right[0]-1, left[0]-1, -1)
            area = max(area, shorter[1] * (right[0] - left[0]))
            
            for i in r:
                if height[i] <= shorter[1]:
                    continue
                shorter[0] = i
                shorter[1] = height[i]
                break
            else:
                break
        return area

 

1. shorter는 list의 주소를 가지기 때문에 shorter의 요소 값을 변경하면 left나 right의 값이 변경됩니다.
2. for ... else 구문을 통해 flag 없이 break로 종료된 상황을 검사할 수 있습니다.

나름의 정리를 해보았지만 그럼에도 코드가 난잡해보이네요...

해설

class Solution(object):
    def maxArea(self, height):
        MAX = 0 
        left = 0
        right = len(height) - 1
        while left != right:
            if height[left] < height[right]:
                area = height[left] * (right - left)
                left += 1
            else:
                area = height[right] * (right - left)
                right -= 1
            MAX = max(MAX, area)
        return MAX

shorter보다 큰 벽을 찾기 위해 내부에 for loop을 둔 것이 코드가 복잡해지는 요인이 되었습니다. 굳이 그럴 필요 없이 양옆으로 줄여가면서 대소 비교를 통해 가장 큰 영역을 구할 수 있습니다.