11. Container With Most Water (O(n)솔루션 존재)

물을 가둘 수 있는 가장 넓이가 큰 값을 구하는 것이다.

 

1. 브루트 포스

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxi = 0
        for i in range(len(height)):
            for j in range(i,len(height)):
                if maxi < (j-i)*min(height[i],height[j]):
                    maxi = (j-i)*min(height[i],height[j])
        
        return maxi
        
        
 # O(n^2) -> 시간초과 발생

dp 문제라고 생각했는데 아니여서 브루트포스로 일단 풀었지만, 시간 초과가 나왔다.

 

2. left, right index 사용

 

가장 최대 넓이가 될 조건은, 일단 index간의 거리가 멀어야하고, 높이가 최대한 높은 것들로만 구성이 되어야 한다.

1. index간 거리가 먼 순서부터 고려해야하므로, left index = 0, right index = len(height)-1 로 시작한다. (가장 멀게)
2. 넓이를 maximum과 비교하고, 두 index중 높이값이 작은 것은 옆으로 한 칸 전진한다.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxi = 0
        left = 0
        right = len(height) - 1
        while left != right:
            if maxi < (right-left)*min(height[left],height[right]):
                maxi = (right-left)*min(height[left],height[right])
            if height[left] <= height[right]:
                left += 1
            else: right -= 1
        
        return maxi

 

시간복잡도 O(n) 알고리즘 해설 동영상

youtu.be/UuiTKBwPgAo