Leetcode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

문제

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

• m * n 2차원 배열이 주어진다.
• 정사각형 내의 숫자들의 합이 threshold 보다 크지 않은 가장 큰 정사각형의 변의 길이를 리턴하시오

예시

• threshold가 4일때 가능한 정사각형의 크기는 2*2 가 가장 크기 때문에 2를 리턴한다.

제한

• $m == mat.length$
• $n == mat[i].length$
• $1 <= m, n <= 300$
• $0 <= mat[i][j] <= 10^4$
• $0 <= threshold <= 10^5$

길이가 300 이하이기 때문에 O(N^2) 까지의 알고리즘은 사용 가능하다.

풀이

class Solution:
    def space(self, start_row: int, start_col: int, end_row: int, end_col: int) -> int:
        init_space = self.prefixes[end_row][end_col]

        removed = 0

        if start_row > 0:
            init_space -= self.prefixes[start_row - 1][end_col]
            removed += 1

        if start_col > 0:
            init_space -= self.prefixes[end_row][start_col - 1]
            removed += 1

        if removed > 1:
            init_space += self.prefixes[start_row - 1][start_col - 1] 

        return init_space


    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        self.ROW = len(mat)
        self.COL = len(mat[0])

        self.prefixes = [[0] * self.COL for _ in range(self.ROW)]

        self.prefixes[0][0] = mat[0][0]

        for r in range(1, self.ROW):
            self.prefixes[r][0] = self.prefixes[r - 1][0] + mat[r][0]

        for c in range(1, self.COL):
            self.prefixes[0][c] = self.prefixes[0][c - 1] + mat[0][c]

        for r in range(1, self.ROW):
            for c in range(1, self.COL):
                self.prefixes[r][c] = self.prefixes[r - 1][c] + self.prefixes[r][c - 1] + mat[r][c]
                self.prefixes[r][c] -= self.prefixes[r - 1][c - 1]

        ans = 0

        for r in range(self.ROW):
            for c in range(self.COL):
                size_available = min(self.ROW - r, self.COL - c)
                for size in range(ans, size_available):
                    s = self.space(r, c, r + size, c + size)
                    if s <= threshold:
                        ans = max(ans, size + 1)
                    else:
                        break

        return ans

1. 2D prefix array를 만들어서 2차원 배열 내 합을 빠르게 구할수 있도록 한다.
2. 시작점을 기준으로 하여 가능한 모든 정사각형을 순회한다.

• 다만! 마지막으로 구한 가장 큰 정사각형의 길이를 기준으로 그것보다 큰것만 순회하여 시간복잡도를 최적화 한다!
• 이렇게 되면 O(N^2)에 모든 정사각형의 순회가 가능하다. 이거 없으면 N^3이 되어 좀 느리다.

O(MN∗logmin(M,N)) 이 드는 이진탐색보다 오히려 낫고, 로직도 간단해서 좋다