[프로그래머스/파이썬] 가장 큰 정사각형 찾기

 

나의 풀이 (시간 초과)

import numpy as np

def solution(board):
    board = np.array(board)
    height, width = board.shape
    
    for n in range(min(height, width), 0, -1):
        for j in range(height - n + 1):
            for i in range(width - n + 1):
                if np.all(board[j:j+n, i:i+n] == 1):
                    return n ** 2
    
    return 0

 

 

 

나의 풀이 (최종 답안)

def solution(board):
    dp = list(board)
    answer = max(board[0])
    for j in range(1, len(board)):
        for i in range(1, len(board[0])):
            if board[j][i]:
                dp[j][i] = min(dp[j-1][i], dp[j][i-1], dp[j-1][i-1]) + 1
        answer = max(answer, max(dp[j]))

    return answer ** 2

 - dp를 이용해야 했던 문제

 - 배열을 순회하면서 지나온 공간에서 만들 수 있는 정사각형의 크기(한 변의 길)를 저장

 - 현재 좌표의 값이 1이라면 지나온 좌표 중에 인접한 세개의 좌표의 최솟값에 1을 더한 값이 됨

     - 세 좌표에서 최대 값으로 겹치는 부분을 생각하면 됨

 - 사실 dp를 만들지 않고 board를 바꿔가면서 나아가도 됨

 

 

 

 

나의 풀이 (개선된 풀이)

def solution(board):
    answer = max(board[0])
    for j in range(1, len(board)):
        for i in range(1, len(board[0])):
            if board[j][i]:
                board[j][i] = min(board[j-1][i], board[j][i-1], board[j-1][i-1]) + 1
        answer = max(answer, max(board[j]))
    
    return answer ** 2