[리트코드] 11. Container with Most Water

리트코드 11번 문제.

난이도: Medium

 

리트코드 링크

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

 

문제

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

예시

Example 1

이미지 1: Example 1

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. 
In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

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

 

답

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

        while left < right:
            h = min(height[left], height[right])
            l = right - left
            maxAreaSoFar = max(maxAreaSoFar, h * l)
            
            if height[left] < height[right]: #1
                left += 1
            else:
                right -= 1

        return maxAreaSoFar

Time Complexity: O(n)

 

설명

이 문제는 가장 큰 컨테이너를 만들 수 있는 두 index를 찾아내 리턴하는 것이다. 문제의 핵심은 포인터 두 개를 이용해서 상황에 가장 최적인 답을 찾고 그에 맞는 가장 적합한 다음 스텝을 찾아내는 것이다. 이 답의 알고리즘은 이렇게 요약해볼 수 있다.

1. 처음에는 가장 넓은 컨테이너에서 시작한다. (가장 처음과 마지막 index) 가장 쉬우면서 정답이거나 정답에 가까운 답 중 하나라고도할 수 있기 때문이다. (넓이가 넓을수록 컨테이너의 전체 크기가 더 커지기 때문에)
2. 처음 컨테이너 (가장 넓은 컨테이너) 보다 더 큰 컨테이너를 만들기 위해서는 무조건 컨테이너의 높이가 더 높아야 한다. (넓이는 처음 컨테이너보다 더 넓을 수 없다.) 또한 컨테이너의 높이는 두 index 중에 하나가 아무리 길어도 더 짧은 index로 한정된다. 그러므로 더 큰 컨테이너를 찾기 위해서는 짧은 index를 옮겨야 한다.
3. 컨테이너를 만든 두 index 중 더 짧은 높이를 가지고 있는 index를 그 옆에 있는 index로 옮겨 새로운 컨테이너를 만든다. 3번을 반복하여 만든 컨테이너마다 면적을 비교해 가장 큰 면적을 리턴한다.

 

짧은 답

...

 

노트

1. 두 index의 높이가 같을 경우는 어떻게 하느냐라고 질문할 수 있다. 이 경우는 두 index 모두 옮길 수 있다. 두 index로 만든 컨테이너보다 더 크게 만들기 위해서는 높이가 무조건 더 높아야 하는데 두 index의 높이가 같을 경우 옮기지 않으면 후에 만들 컨테이너의 높이는 무조건 지금 만든 것보다 작거나 같을 수밖에 없기 때문이다. 그러므로 이 경우를 if문에  추가하여 더 효율적이게 만들 수도 있다.
2. 답의 #1 블록 if문에서 left와 right를 하나씩만 더 옮겼는데 이것보다 더 효율적이게 하려면 if와 else문 아래에 while루프 하나를 더 추가해서 각 height가 h (left와 right의 minimum) 보다 더 높아질 때까지 계속 옮기게 할 수 있다. height가 h보다 더 낮으면 컨테이너를 만들어봤자 그 크기가 더 작을 수밖에 없기 때문이다.

 

출처

이미지 1: https://leetcode.com/problems/container-with-most-water/description/