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

🍒문제

programmers.co.kr/learn/courses/30/lessons/12905?language=python3

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

 

🍒풀이

전형적인 DP문제.

처음에 이 문제를 for문을 돌려 풀었더니 O(N^3)의 시간복잡도가 나와 효율성에서 시간초과가 났다.

따라서 시간복잡도를 줄이기 위해서 DP를 적용해서 풀어야한다.

이 문제에서는 메모이제이션(memoization) 기법을 사용하는데, 왼쪽 위에서부터 index를 업데이트를 해준다.

해당 칸 (board[y][x])의 값이 1이면 왼쪽, 위, 대각선왼쪽 위 3부분을 확인해서 가장 작은 값 + 1 로 업데이트 해준다.

 

최종적으로 가장 큰 값의 index를 제곱하여 가장 큰 정사각형의 넓이를 answer로 출력한다.

 

🍒코드

def solution(board):
    answer = 1234
    w = len(board[0])
    h = len(board)
    
    for y in range(1, h):
        for x in range(1, w):
            if board[y][x] == 1:
                board[y][x] = min(board[y-1][x-1], min(board[y-1][x], board[y][x-1])) + 1
    
    max_val = 0
    for i in range(h):
        for j in range(w):
            max_val = max(max_val, board[i][j])
    answer = max_val**2
    
          
    return answer