[Java] 프로그래머스 Lv.2 : 가장 큰 정사각형 찾기

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

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

 

풀이

해당 문제의 규칙은 다음과 같다.

1. 행 또는 열의 길이가 1이면 정사각형의 넓이는 1이다.
2. 루프를 돌아 자신의 위치([i][j])의 값이 0이 아닌 경우, 자신의 기준으로 왼쪽상단(↖), 왼쪽(←), 위쪽(↑) 의 최솟값을 구한뒤, 자신의 위치에 최솟값+1을 할당한다.
3. 그렇게 구한 board값 중 최댓값을 answer에 할당 해준 뒤 answer*answer로 정사각형 넓이를 구해 리턴한다.

2번의 최솟값이 0이상인 경우엔 1로 이루어진 정사각형이 만들어 진다는 것이고, 그 최솟값에 +1을 할당해주는 것은 한 변의 길이를 1씩 더해주는 것과 같다.

따라서 한 변의 길이의 최댓값에 제곱을 해주면 가장 큰 정사각형을 구할 수 있다.

 

전체코드

class Solution{
    public int solution(int [][]board){
        int answer = 0;
        int row = board.length;
        int col = board[0].length;
        
        // board의 행 또는 열이 1로 주어질 때 예외처리
        if(row<2||col<2){
            return 1;
        }
        
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                if(board[i][j] !=0){                
                    // board[i][j]의 왼쪽 상단, 왼쪽, 위쪽 중 최솟값 구해서 +1 후 할당
                    board[i][j] = Math.min(board[i-1][j-1],Math.min(board[i-1][j],board[i][j-1]))+1;
                }                
                // 그 중 최댓값을 answer에 할당
                if(answer < board[i][j]) answer = board[i][j];
            }
        }

        return answer*answer; // 정사각형 넓이
    }
}