11. Container With Most Water (+Python)

문제:

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

 

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.

---

문제를 보자면 막대기들의 배열을 받습니다. 최대로 물을 채울 수 있는 부피를 구하는 것이 이 문제의 핵심입니다.

#브루스포스 방식
class Solution:
    def maxArea(self, height: List[int]) -> int:
        answer= set()
        for i in range(len(height)-1):
            for j in range(i+1,len(height)):
                if i != j:
                    area = min(height[i],height[j])
                    w = j-i
                    answer.add(area*w)
        return max(list(answer))

 

처음 문제를 보면서 브루스포스로 풀어보았습니다. 모든 상황을 고려하여 set() 배열에 넣은 다음 max를 뽑아 출력합니다. 이때 시간 복잡도는 n^2로 타임아웃 발생합니다. 그 다음으로 접근했던 방식은 모든 상황을 고려하지 않아도 될 수 있을 것 같아 투 포인터로 접근해보았습니다.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        answer= set()
        l = 0
        r = len(height)-1
        while l != r:
            if height[l]<=height[r]:
                h  = min(height[l],height[r])
                w = r-l
                answer.add(h*w)
                l+=1
            else:
                h  = min(height[l],height[r])
                w = r-l
                answer.add(h*w)
                r-=1
                
        return max(list(answer))

먼저 이 방법의 시간복잡도는 n입니다. 브루스 포스에 비해 훨씬 빠릅니다. 풀이를 보자면 left와 right의 값으로 양끝을 지정해줍니다. left와 right가 만날 때까지 while문을 돌려줍니다. 만약 왼쪽 높이가 오른쪽 높이보다 작거나 같다면 부피를 구한 다음 set() 배열에 넣어주고 left의 값을 1증가시켜줍니다. 반대일 경우 오른쪽의 값을 -1해 줍니다. set() 배열에서 max값을 뽑아주고 반환해줍니다. 

 

문제의 의도를 정확하고 빠르게 파악 후 풀이를 진행하는 것이 중요하다고 느꼈습니다.