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

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

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

풀이

문제를 보았을때 알수있는 힌트

이러한 정사각형 문제는 많이 풀어봐야지 감이 잡힐것같다. 40분 가량 봐도 답이 나오지 않아서 다른 사람들의 푸는 방식을 통해 힌트를 얻고 풀었다. 

 

2가지 조건을 두고 문제를 푼다.

1. i+1,j+1이 0이면 넘어가고 1인 경우 2번의 조건을 수행한다.

2. i,j와 i+1,j와 i,j+1의 값 중 최소 값에 1을 더하여 i+1,j+1에 넣는다.

이것을 반복하여 나온 board의 최대값을 제곱하면 끝나는 문제이다.

 

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

https://github.com/dydwkd486/coding_test/blob/main/programmers/가장%20큰%20정사각형%20찾기.py 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리