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

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

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

처음에는 어떻게 풀어야할지 막막해서 고민을 하다. 3중 for문을 통해 문제를 해결하려 했다.

#프로그래머스 가장 큰 정사각형 찾기
def solution(board):
    line=0
    N=len(board)
    M=len(board[0])
    for i in range(N):
        l=[1]*(M)
        for j in range(i,N):
            count=0
            cnt=0
            for k in range(M):
                l[k]=board[j][k]*l[k]
                if l[k]==1:
                    count+=1
                elif l[k]==0:
                    cnt=max(cnt,count)
                    count=0
            cnt=max(cnt,count)
            if (j-i+1)<=cnt:
                line=max(line,(j-i+1))
    answer=line**2
    return answer

다음과 같은 코드를 실행하니 효율성테스트에서 시간초과가 발생하였다.

고민하다가 결국 다른 분 아이디어를 참고하여 dp로 해결하였다.

#프로그래머스 가장 큰 정사각형 찾기 

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

borad[i][j]가 1이면, 왼쪽, 왼쪽아래, 아래의 min의 값을 찾고, 1을 더한다. (왼쪽 왼쪽아래 아래 모두가 1이면 borad[i][j] 값이 1증가)

최종적으로 answer을 구한다.