[프로그래머스][Level2][Java] 가장 큰 정사격형 찾기

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

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

문제풀이

레벨2문제 치고는 상당히 어려웠다. DP에 약해서 그런거 같다.

처음보자마자 브루트 포스로 풀 수 있지 않을까 생각했지만 Row의 길이가 1000, Col의 길이가 1000인데다가

1000x1000일때 정사각형의 크기를 1씩 증가시키면 O(N^3)이 되어 버린다. 그래서 무조건 DP를 이용해서 풀어야겠구나 생각하였다.

 

위와 같이 크기의 2x2로 board[1][1]로 봤을때 왼쪽, 위쪽, 대각선 중에서 최소값의 +1을 해주면 사각형의 길이가 된다.

위 5번 그림처럼 전부 2이면 위쪽부터 정사각형이 된다는 것을 의미함으로 +1의 해주면 정사각형의 길이가 된다. 

check변수를 쓴 이유는 정사각형의 크기가 1만 존재할 경우와 전부 0일때를 구분하기 위해서 사용하였다.

전체 배열을 check하면서 가장 큰 값을 저장해서 제곱 해주면 원하는 값이 된다.

 

코드

class Solution
{
   public int solution(int [][]board)
    {
        int answer = 0;
        int N = board.length;
        int M = board[0].length;
        boolean check = false; // 1이 있는지 체크
        //i ==1, j==1부터 시작때문
        if(board[0][0] == 1 || board[1][0] == 1 || board[0][1] ==1) check = true;
        
        for(int i=1; i<N; i++){
            for(int j=1; j<M; j++){
            	if(board[i][j] == 0) continue;
            	check = true;
                int min = Math.min(board[i-1][j-1], board[i-1][j]);
                min = Math.min(board[i][j-1], min) +1;
                //정사각형 X
                if(min == 1) continue;
                board[i][j] = min;
                answer = Math.max(answer, min);
            }
        }
        
        //넓이가 1만 존재하는 경우
        if(answer==0 && check) return 1;
        return answer*answer;
    }
}