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

링크 programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

 

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

코드

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

1. 기본적으로 board안에 1이 없을 수도 있으므로 answer의 초기값은 0으로 했다. 그런데 board안에 1이 없는 경우에도 답 1로 해도 맞는거보니 테스트케이스가 부족한 것 같다. 아니면 문제에 1이 하나 이상있다는 조건이 있어야했다.

2. len(board)<2이고 board안에 1이 있으면, 가장 큰 정사각형의 크기는 1이다. 

3. 이중 for문을 1<=i<len(baord), 1<=j<len(board[i]) 범위로 돌리면서 만약 board[i][j]가 1이면 board[i][j]와 board[i][j]의 왼쪽, 위쪽, 왼쪽위의 값의 최소값에서 1을 더한 값을 board[i][j]로 했다.

4. 그리고 이전 값과 비교해서 제일 큰 값이 정답으로 들어가게 했다.

5. 가장 큰 정사각형의 길이가 answer에 들어가있으므로 answer을 제곱해서 카장 큰 정사각형의 크기(넓이)를 리턴해준다.