[Leetcode/medium] 11. Container With Most Water

아마존 인터뷰 시리즈 중에 있어서 풀어봄

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

 

easy 문제인줄 알았는데 나중에 보니 medium문제네...

(그렇다고 쉽게 푼것도 아님)

 

막상 풀려고 보면 brute force로 푸는게 바로 생각남...

실제로 그렇게 푸는 문제는 거의 없으니 아닐게 분명하고..

 

힌트를 살짝 봤다

1번힌트: n^2은 아님 (.......그건 나도 알아....)

 

어쩔 수 없이 2번 힌트

2번힌트: 포인터 2개를 사용해서 값이 작은 쪽을 이동해라

 

아 듣는순간 해결방법이 바로 떠오름

좌우에서 그리디하게 현재 바가 더 짧은 것을 중앙쪽으로 이동시키면서 최대 면적을 탐색하면 되는구나...

최대 면적 탐색에서 순간순간 그리디한 선택을 하면서 굳이 확인해보지 않아도 되는 케이스는 건너 뛰는 방식

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        p1 = 0
        p2 = len(height) - 1
        
        max_area = 0
        while(p1 < p2):
            w = p2 - p1
            h = min(height[p1], height[p2])
            area = w * h
            max_area = max(max_area, area)
            
            if height[p1] < height[p2]:
                p1 += 1
            else:
                p2 -=1
            
        return max_area

 

오늘도 하나 배우고 갑니다...