LeetCode 11(Container With Most Water, python)

1. 문제 링크

• LeetCode - The World's Leading Online Programming Learning Platform

Container With Most Water - LeetCode

2. 문제 설명

• 리트 코드의 문제 설명이 이상하다. 물의 양을 생각하면 헷갈림.
• 그냥 이렇게 생각하자. 일정 간격으로 높이가 제각각인 막대기들이 있음.
• 임의의 두 막대로 만들 수 있는 직사각형의 넓이의 최댓값 구하기. (직사각형의 높이는 두 막대 높이 중 min 값)

3. 처음 풀이

• 임의의 두 막대를 선택하는 경우를 모두 고려하면 시간복잡도가 O(n²)인데 이는 좋은 풀이가 아님
• two pointers 방법을 이용하면 O(n)으로 풀 수 있음.
• 첫 후보는 좌우 양 끝 막대를 고르는 것(가로가 제일 길기 때문에 적당한 후보임.)
• 이제 좌우 경계를 조금씩 안으로 좁히며 넓이의 최댓값을 업데이트하며 좌우 경계가 만날 때까지 탐색하면 O(n)으로 풀 수 있음.
• 좌우 경계를 안쪽으로 좁히는 방법.
  • 두 막대기 중 높이가 크지 않은 값이 사각형의 높이가 됨.
  • 막대기가 안쪽으로 가면 가로가 작아지므로 넓이가 커지려면 무조건 사각형의 높이가 커져야 함.
  • 그렇다면 두 막대 높이의 min 값이 커져야하므로 둘 중 작은 막대가 안쪽으로 가면서 더 높은 막대가 되어야 함.
  • 따라서 두 막대 중 작은 막대를 안쪽으로 옮기며 원래보다 높은 막대가 될 때까지 옮겨주고 이때 넓이를 구하여 업데이트. 반복.
  • 이때 좌우 막대의 높이가 같을 때 어느 막대를 먼저 옮기는 지는 답에 영향을 미치지 않음.
  • 왜냐하면 두 막대 높이가 같은 순간이 생겼을 때, 안쪽으로 왔을 때 더 큰 넓이가 발생하려면 좌우 모두 안쪽으로 왔을 때 높이가 커져야 함. 그렇다면 결국 무엇을 먼저 옮기든 나머지 하나도 그 다음에 옮겨짐.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        result = (len(height)-1)*min(height[0],height[-1]) #처음 넓이
        l = 0 #왼쪽 경계
        length = len(height) #리스트 길이
        r = length-1 #오른쪽 경계

        while l < r : #두 경계를 점점 안쪽으로 이동하다가 만나거나 역전될 때까지 반복
            heightLeft = height[l] #왼쪽 높이
            heightRight = height[r] #오른쪽 높이
            if heightLeft < heightRight: #두 경계 중 높이가 낮은 경계(지금 왼쪽)를 안쪽으로 이동
                x = l
                while heightLeft >= height[x] and x < length: #안쪽 경계가 더 낮아지면 넓이가 커질 수 없으므로 +1 칸 안쪽 이동
                    x += 1
                l = x
            else: #오른쪽 경계 높이가 더 낮다면 안쪽으로 이동
                y = r
                while height[y] <= heightRight and y > 0: #안쪽 경게가 더 낮아지면 넓이가 커질 수 없으므로 -1 칸 안쪽으로 이동
                    y -= 1
                r = y
            result = max(result, (r-l)*(min(height[l],height[r]))) #안쪽 경계가 높아졌다면 넓이 계산하여 최댓값 업데이트

        return result

4. 다른 풀이

• 두 막대 중 낮은 막대를 안쪽으로 옮길 때 그냥 한칸씩 옮기며 모두 업데이트하는 풀이

class Solution:
    def maxArea(self, height: List[int]) -> int:
        start_point = 0 
        end_point = len(height)-1
        output = 0 

        while(start_point != end_point):
            if height[end_point] > height[start_point]:
                area = height[start_point] * (end_point - start_point)
                start_point += 1
            else:
                area = height[end_point] * (end_point - start_point)
                end_point -= 1

            if area > output:
                output= area

        return output

5. 배운 점

• two pointer 기법을 이용하면 O(n²)을 O(n)으로 단축할 수 있음.
• 포인터 두 개가 모두 왼쪽이 아니라 왼쪽 하나 오른쪽 하나에서 출발하는 경우는 처음 풀어봄.