[프로그래머스] 가장 큰 정사각형 Java

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12905
레벨 : Level 2
분류 : 연습문제

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

이 문제는 주변 요소를 이용하여 정사각형의 크기를 구하는 문제이다.

 

DFS, BFS와 비슷해 보이긴 했지만 전혀 구상해내지 못하였다. 

그래서 다른 사람의 풀이를 보고 코드를 분석해가며 풀었고 이 유형의 문제를 처음 접한 것 같다.

다른 사람의 문제 풀이 방식을 학습하고 나서 구현은 쉽게 할 수 있었다.

하지만 예외를 찾지 못해서 한참을 헤맸는데 찾은 예외는 1X1를 대처하지 못하였다.

그래서 1X1을 대처하기 위해 결과 배열의 크기를 1행 1열씩 더 크게 정의하여 해결하였다.

 

아래와 같이 풀이를 공유합니다.

class Solution
{
    public int solution(int [][]board)
    {
        int answer = Integer.MIN_VALUE;
        
        int[][] map = new int[board.length+1][board[0].length+1];
        
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                map[i+1][j+1] = board[i][j];
            }
        }
        
        
        for(int i = 1; i < map.length; i++) {
            for(int j = 1; j < map[0].length; j++) {
                if(map[i][j] != 0) {
                    int min = Math.min(map[i-1][j-1], Math.min(map[i-1][j], map[i][j-1])) + 1;
                    map[i][j] = min;
                    answer = Math.max(answer, min);    
                }
            }
        }
        
        return answer * answer;
    }
}