Maximal Square

LeetCode - The World's Leading Online Programming Learning Platform

문제 파악 [필수 작성]

문제이해

1로 채워진 가장 큰 정사각형의 넓이를 구해라

제한 조건 확인

최대 300x300 매트릭스
입력값은 0,1 로 제한

아이디어

열 행 기준으로 이중 포문 탐색
(i,j )를 탐색할때 (i,j), (i-1,j), (i,j-1), (i-1,j-1) 중 0이 한개라도 있으면 pass
만약 다 0이 아닌 값이면, 3개중 min값을 +1 한 값을 해당 위치에 저장

시간복잡도

3x300x300 = 270,000

자료구조

접근 방법 [필수 작성]

아이디어

코드 구현 [필수 작성]

1차 시도

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        max_val = 0

        for c in range(n):
            for r in range(m):
                matrix[r][c] = int(matrix[r][c])

        for c in range(1,n):
            for r in range(1,m):
                if not (matrix[r][c] and matrix[r-1][c] and matrix[r][c-1] and matrix[r-1][c-1]):
                    pass
                else:
                    matrix[r][c] = min(matrix[r-1][c],matrix[r][c-1],matrix[r-1][c-1]) + 1
        
        for c in range(n):
            for r in range(m):
                max_val = max(max_val,matrix[r][c])

        return max_val**2

2차 시도

코드 최적화

이중포문 하나로 줄였는데 오히려 연산시간 늘어남..

→ 연산량은 어차피 비슷하다.. 오히려 max_val 가 빈번하게 업데이트가 일어나면서 연산량이 늘어난게 아닐까 추정

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        max_val = 0

        for c in range(n):
            for r in range(m):
                matrix[r][c] = int(matrix[r][c])
                if r == 0 or c == 0:
                    max_val = max(max_val,matrix[r][c])
                    continue
                elif not (matrix[r][c] and matrix[r-1][c] and matrix[r][c-1] and matrix[r-1][c-1]):
                    max_val = max(max_val,matrix[r][c])
                    pass
                else:
                    matrix[r][c] = min(matrix[r-1][c],matrix[r][c-1],matrix[r-1][c-1]) + 1
                    max_val = max(max_val,matrix[r][c])
                    
        return max_val**2

3차 시도

코드 최적화

코드의 구조자체를 바꾸어, dp_table 을 생성하면서 진행되는 형식

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        dp_table = []
        max_val = 0

        for r in range(m):
            dp_list = []
            for c in range(n):
                if r == 0 or c == 0:
                    dp_list.append(int(matrix[r][c]))
                elif matrix[r][c] == '1': 
                    dp_list.append(min(dp_table[r-1][c],dp_list[c-1],dp_table[r-1][c-1]) + 1)
                else:
                    dp_list.append(int(matrix[r][c]))
            max_val = max(max_val,max(dp_list))
            dp_table.append(dp_list)
                    
        return max_val**2

배우게 된 점 [필수 작성]

자유 형식

질문 [ 필수 X ]