[코딩 문제 풀이(파이썬/Python)] 프로그래머스 _ 가장 큰 정사각형 찾기

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

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

[문제 설명]

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

예를 들어

1234

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형의 넓이는 9가 되므로 9를 반환해 주면 됩니다.

[제한 조건]

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

아래는 내가 짠 효율성에서 탈락한 코드,,,,,

간절하게 살리고 싶었으나 방법이 없는 듯 하다. 하루 종일 했는데..

최대 1000 = 10^3에 대해 for문이 3번 돌아가 10^9 연산이 된다고 한다.. break도 잘 주고, 나름 필터링도 있는데 이정도로는 택도 없나보다.........

# 시작지점 잡고, 체크하기 -> 정확도 100%, 시간초과(1)
def solution(board):
    check = 0 ; length = min(len(board), len(board[0])) +1
    string = list(map(lambda x: ''.join((map(str, x))).replace('0', 'x'), board))
    if ''.join(string).isalpha():
        return 0
    else:
        while (check ==0) and (length != 0):
            length -= 1 
            starts = [(i,j) for i in range(len(board)-length+1) 
                    for j in range(len(board[0])-length+1)
                     if board[i][j] == 1]
            for i,j in starts:
                cnt = 0
                for y in range(i, i+length):
                    if 'x' in string[y][j:j+length]:
                        break
                    else:
                        cnt += 1
                if cnt == length:
                    check+=1
                    break
    return length**2

# 시작지점 잡고, 체크하기 -> 정확도 100%, 시간초과(2)
def solution(board):
    check = 0 ; length = min(len(board), len(board[0])) +1
    while check ==0:
        length -= 1 
        starts = [(i,j) for i in range(len(board)-length+1) for j in range(len(board[0])-length+1)]
        for i,j in starts:
            cnt = set([set(board[y][j:j+length]) == {1} for y in range(i, i+length)])
            if 0 in cnt:
                continue
            else:
                check+=1
                break
    return length**2

 

처음으로 답을 내기 전에 다른 사람의 풀이를 참고했다.. 기준이 되는 1을 찾은 뒤, 그 1을 포함하는 최대 정사각형의 변의 길이로 그 cell의 내용을 업데이트 해나가는 방법이다. 이중 for문 내에서 해결 가능한게 차이인가보다,,

# 동적 프로그래밍(DP_Dynamic Programming)을 활용한 풀이
def solution(board):
    row = len(board)
    col = len(board[0])
    for i in range(row):
        for j in range(col):
            if i == 0 or j == 0:
                continue
            if board[i][j] != 0:
                board[i][j] = min(board[i-1][j-1],min(board[i-1][j],board[i][j-1]))+1
    answer=[]
    for i in range(row):
        answer.append(max(board[i]))
    return max(answer)**2