[Leetcode] Container With Most Water

solution for Container With Most Water

 

 

Problem)

 

 

Solution)

2개의 포인터를 활용해서 시간 복잡도 O(n)에 끝낼 수 있다. 

max_water 변수에는 각 단계별 최대 물의 양을 저장한다. x, y 포인터 초기화하고 각각 x는 시작점, y는 끝점에 위치하고 하나씩 옮기며 최대 물의 양을 계산하고 max_water의 값과 비교하여 최종 최대 물의 양 값을 얻는다. 이때 포인터를 옮기는 과정에서 x, y 포인터가 가르키는 막대의 길이를 비교하여 길이가 짧은 막대의 포인터를 x는 +1, y는 -1로 한칸씩 옮겨야 한다. 

 

Example의 예를 들면 최초 x는 0 (height[0] = 1)을 가르키고 y는 8 (height[8] = 7)을 가르킨다. 여기서 물의 양을 계산하면 (막대 간 거리) * (짧은 쪽 막대 높이) = (y - x) * height[x] = 8이 된다. 그 다음 x가 가르키는 막대의 길이가 1로 y가 가르키는 막대의 길이 7보다 짧기 때문에 x 포인터를 +1 하여 다음 막대를 가르키게 된다. 그러면 다음번 계산에서는 (y - x) * height[y] = (8-1) * 7 = 49가 되고 결과적으로 예제 문제의 답이 된다.

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_water = 0
        x, y = 0, len(height)-1
        
        while x < y:
            if height[x] < height[y]:
                max_water = max(max_water, (y-x)*height[x])
                x += 1
            else:
                max_water = max(max_water, (y-x)*height[y])
                y -= 1
                
        return max_water
            

 

 

메모리 효율이 더 좋은 코드를 고민 해야겠다..