Programmers 12905 - 가장 큰 정사각형 찾기

코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스 스쿨

프로그래머스

 

1과 0으로 이루어진 2차원 배열 board에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 반환

먼저 떠오르는 방식은 완전 탐색이다. 모든 가능한 정사각형의 크기를 다 확인하는 것이다. 하지만 이는 시간복잡도 O(n^2m^2)으로 비효율적이다.

따라서 dp를 생각해 보자.

dp[i][j]에서의 최대 정사각형의 크기는 어떻게 판단할까?

dp[i][j]에서의 최대 정사각형은 min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1이 된다.

import java.util.*;

class Solution
{
    public int solution(int [][]board)
    {
        for (int i = 1; i < board.length; i++) {
            for (int j = 1; j < board[i].length; j++) {
                if (board[i][j] == 1) {
                    board[i][j] += Math.min(board[i - 1][j], Math.min(board[i][j - 1], board[i - 1][j - 1]));
                }
            }
        }
        
        int x = Arrays.stream(board).flatMapToInt(Arrays::stream).max().getAsInt();

        return x * x;
    }
}