[medium] 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cut

문제

https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/description/

---

풀이방법

가장 큰 사각형을 만드려면 가로와 세로가 각각 최대이면 된다.
가로가 최대인 것을 찾으려면 0, horizontalCuts, h 사이의 간격들 중에 가장 긴 부분을 길이를 찾아서 저장한다.
그런데 이 때 example2 처럼 horizontalCuts 혹은 verticalCuts 가 정렬되어있지 않을 수 있으므로, 먼저 정렬해주고 최대길이를 찾아야 한다.

비슷하게 세로가 최대인 것을 찾으려면 0, verticalCuts, w 사이의 간격들 중에 가장 긴 부분을 길이를 찾아서 저장한다.
그 다음이 가로최대길이와 세로최대길이의 곱을 10^9+7로 나눈 나머지를 출력해주면 된다.
시간복잡도 O(N*M). N은 len(horizontalCuts), M은 len(verticalCuts)

반응형

---

코드

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        
        maxh = 0
        maxw = 0
        prev = 0
        for i in horizontalCuts:
            if i-prev > maxh:
                maxh = i-prev
            prev = i
        if h-prev > maxh:
            maxh = h-prev
        prev = 0
        for i in verticalCuts:
            if i-prev > maxw:
                maxw = i-prev
            prev = i
        if w-prev > maxw:
            maxw = w-prev
        result = (maxh*maxw) % (10**9 + 7)
        return result