[99클럽 코테 스터디 17일차 TIL] LeetCode | 11. Container With Most Water

17일차 알고리즘

Problem

https://leetcode.com/problems/container-with-most-water/

 

Sol

가장 많은 물을 담을 수 있는 컨테이너를 만들고 그 양을 찾는 문제

 

Greedy Algorithm ? Two-pointer ?

 

• two-pointer 접근법
  1. 포인터를 배열의 처음과 끝에 둡니다.
  2. 포인터가 양끝에서 시작하여 중앙으로 이동하면서 현재 가능한 최대 면적을 유지합니다.

현재 가능한 최대 면적을 유지한다는 점에서 탐욕스러운 greedy algorithm 중 하나로 불리는 것 같습니다.

 

해결 방법

👀 컨테이너의 너비를 최대로 시작하여 점점 좁히는 형식으로 접근하였습니다. 

1. 시작과 끝에서 점점 좁히기 : 시작점에 left 포인터, 끝 점에 right 포인터 설정
2. 면적 구하기 : right-left로 width, 수조에 물이 담겨야 하기 때문에 둘 중 더 낮은 지점을 height로 설정
3. 낮은 높이 버리고 포인터 이동 : (Greedy 한 측면) 결일단 높이가 낮은 쪽을 포기하고 포인터를 이동시켜 안으로 점점 좁힘
4. 반복

 

시간복잡도 O(n)

• 배열 순회(n개) : O(n)

💡 O(n^2)의 시간복잡도를 가지게 되는 모든 쌍을 조합해보는 것 보다 효율적입니다!

---

✔ Answer

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 가장 많은 물을 담을 수 있는 컨테이너 만들기
        # max_area : w*h 
        
        # 1. left and right 끝과 끝에서 좁히기
        left = 0
        right = len(height)-1
        max_area = 0
        
        # 2. 최대 면적 구하기
        while left<right:
            # 너비
            w = right-left
            
            # 높이 : 더 낮은쪽
            h = min(height[left], height[right])
            
            # 면적
            area = w * h
            max_area = max(max_area, area)
            
            #3.  Greedy 일단 낮은 쪽을 버림(이동)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_area

---

💬 소감

방법을 조금만 익히면 풀 수 있는 문제가 많아지는 것 같아서 점점 재밌어지는 중입니다 :)