[LeetCode]Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/

Container With Most Water - LeetCode

 

문제 분석

주어진 높이와 길이를 가지고 가장 많은 양의 물을 담을 수 있는 컨테이너의 크기를 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # Use two pointers.
        left = 0
        right = len(height) - 1
        max_container = 0

        # Repeat until just before the two pointers meet. Equal the distance(right - left) difference is 1.
        while(left < right):
            min_height = min(height[left], height[right])
            # It should be a min_height * distance so that the water does not overflow.
            max_container = max(max_container, min_height * (right-left))

            # Move the pointer to a smaller height as we need a higher height to contain more.
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_container

접근 방법

1. left는 맨 왼쪽, right는 맨 오른쪽에서 시작합니다.
2. left, right 두 커서가 만날때까지 반복합니다.
3. 물을 담는 컨테이너의 높이는 left 와 right 중 작은 높이에 의해 결정됩니다. 컨테이너의 가로 길이는 두 커서의 차이 입니다.
4. 두 커서의 차이 * 낮은 높이의 값과 이전의 max_container중 큰 값을 max_container로 저장합니다.
5. left 커서의 높이가 낮다면 left 커서를 한칸 오른쪽으로, right 커서의 높이가 낮다면 right 커서를 한칸 왼쪽으로 움직입니다.
6. 두 커서가 만나게 되면 반복을 종료하고 max_container 값을 구할 수 있습니다.

이 문제도 두개의 포인터를 활용하는 방법으로 해결할 수 있습니다. 양 끝에 커서를 위치시키는 식으로 시작하며 물을 더 많이 담기 위해서는 높은 높이가 필요하므로 작은 높이의 커서를 한칸씩 움직입니다. 움직이고 난 뒤에는 값을 비교하고 큰 값을 저장시켜둡니다.

 

막상 해설을 보면 굉장히 쉬워보이지만 이 아이디어 자체를 떠올리는 것이 쉽지 않았습니다. 많은 연습이 필요한 것 같습니다.