leetcode 11. Container With Most Water 풀이

문제 : 아래 그림과 같이 높이에 대한 list가 주어졌을 때, 가장 많은 물을 담은 경우의 output을 반환하라

 

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

아이디어 : for 문 두 개를 사용해서 탐색할 시 timeout 이 발생하므로 while 문을 사용하며 상태를 변화시키며 탐색한다.

두 개의 height 중 작은 쪽을 사용하는 것을 이용하여, 양극단에서 시작해서 두 개를 비교하여 작은 쪽의 index를 가운데로 이동하면서 탐색한다.

 

코드 :

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        max_area = 0
        s = 0
        e = n-1
        while s < e:
            max_area = max(max_area, (e-s)*min(height[s], height[e]))
            if height[s] < height[e]:
                s += 1
            else:
                e -= 1
        return max_area

 

학습 포인트 : 이것도 일종의 two point에서 출발하는 탐색이라고 생각한다.

문제의 조건을 잘 파악하는 능력을 키우자.

 

출처 : leetcode.com/problems/container-with-most-water/