[프로그래머스] 레벨2 가장 큰 정사각형

https://programmers.co.kr/learn/courses/30/lessons/12905?language=java# 

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

 

이 문제는 DP를 활용한 문제였고 그 외 다른 스킬이나 지식은 필요없었던 것 같다. 기본적인 구현은 금방했지만, 예외케이스에 대한 경우(TC 8번 : 모두 0인 경우)를 못 떠올려서 생각보다 오래 걸린 문제였다.

1. 배열 board보다 가로, 세로 줄이 한 칸씩 더 큰 배열 square을 만들어서 맨 윗줄과 맨 왼쪽 줄을 모두 0으로 초기화

2. square로 board의 값 옮기기 (index 주의)

3. DP 적용

  3-1. 해당 칸(square[i][j])이 0일 경우 스킵

  3-2. 해당 칸(square[i][j])이 0이 아닐 경우 square[i-1][j-1], square[i][j-1], square[i-1][j] 세 개 중 작은 걸 골라서 +1

  3-3. 결과값으로 리턴할 max 변수 업데이트

4. max 제곱해서 리턴

  4-1. 단, max가 0일 경우 강제로 0을 리턴 => 이 경우를 생각하지 못해서 시간이 오래걸렸다.

 

---

 

문제

 

제한사항 및 입출력

 

---

 

코드

class Solution
{
    public int solution(int [][]board)
    {
        // DP배열 및 비교값 변수 선언
        int[][] square = new int[board.length+1][board[0].length+1];
        int max = Integer.MIN_VALUE;
        
        // DP배열 초기화(0으로 테두리 만들기)
        for(int i=0; i<board.length; i++)
        {
            square[i][0] = 0;
        }
        for(int i=0; i<board[0].length; i++)
        {
            square[0][i] = 0;
        }

        //  DP용 배열에 값 할당
        for(int i=1; i<=board.length; i++)
        {
            for(int j=1; j<=board[0].length; j++)
            {
                square[i][j] = board[i-1][j-1];
            }
        }
        
        //  0이 아닐 경우, square[i][j] = square[i-1][j-1], square[i][j-1], square[i-1][j]의 최소값+1
        for(int i=1; i<=board.length; i++)
        {
            for(int j=1; j<=board[0].length; j++)
            {
                if(square[i][j]!=0)
                {
                    square[i][j] = Math.min(Math.min(square[i-1][j-1], square[i-1][j]), square[i][j-1])+1;
                    max = Math.max(max, square[i][j]);
                }
            }
        }
        
        // 모든 값이 0일 경우에는 강제로 0 리턴
        return max==Integer.MIN_VALUE?0:(int)Math.pow(max,2);
    }
}