[프로그래머스] Level 2 - 가장 큰 정사각형 찾기 (Python)

 

 

 

 

https://programmers.co.kr/learn/courses/30/lessons/12905

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

 

 

 

 

✅ Solution

• 정사각형이 되기 위해서는 최소한 위, 왼쪽, 왼쪽 대각선의 값이 0이 아니여야 하는 것을 이용한다.
• 만약 위, 왼쪽, 왼쪽 대각선의 값이 모두 0이 아니라면 정사각형이 될 수 있다는 의미이므로 그중 최솟값을 찾아 1을 더해준다.
• row나 col이 1 일수 있으므로 board [0][0] 값에 따라  answer 초기값을 정해준다.

 

 

 

 

✅ Code

def solution(board):
    answer = 0 if not board[0][0] else 1

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

    return answer * answer