Level 2. 가장 큰 정사각형 찾기

가장 큰 정사각형 찾기

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

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

문제 설명

• Input value = 2D array composed with 0,1(int)
  - 1 <= row, column <= 1,000
  
• Output value = max(square area composed with 1(int))

문제 구상

1. 원소 위치를 정의하기 위한 rows, colums 설정

m, n = len(board), len(board[0])

2. array에 있는 모든 원소에 대하여,

for i in range(1, m):
    for j in range(1, n):

3. 원소 값이 1일 경우, 원소 주변의 board[i-1][j-1], board[i-1][j], board[i][j-1])의 최소값에 1을 더하여 원소값을 갱신한다.

        if board[i][j] == 1:
            board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1

4. 해당 과정 종료 후 itertools.chain을 이용한 뒤, 최대값^2 return

문제 풀이

import itertools

def solution(board):
    m, n = len(board), len(board[0])
    for i in range(1, m):
        for j in range(1, n):
            if board[i][j] == 1:
                board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1

    return max(itertools.chain(*board))**2
    
# Code test
board = [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]
solution(board)