[Programmers] LV2 - 가장 큰 정사각형 찾기

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

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

 

 

알고리즘 분류 : Dynamic Programming

 

문제 파악

 

주어진 배열에서 1로만 이루어진 가장 큰 정사각형을 찾아서 그 정사각형의 넓이를 반환하면 되는 문제이다.

 

문제 해결 과정에서 처음은 Brute force 하게 풀어보았고 두 번째로 DP로 문제를 해결하였다.

 

1. Brute Force ( 정확성 All pass , 효율성 All fail)

 

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;

        //brute force 하게 풀어 보자.        
        int row = board.length;
        int col = board[0].length;
        
        int size = Math.min(row,col); //최대 길이 부터 감소하는 식으로
        
        loop: while(size>=0){
        for(int w = 0; w+size <=row;w++)
        {
            for(int h = 0; h+size<=col;h++)
            {
                boolean check = findRectangle(board,w,h,size);                
                if(check){
                    answer = (size) * (size);
                    break loop;
                }
            }
        }
            size--;
        }
        return answer;
    }
    public boolean findRectangle(int[][] board,int sw,int sh, int size)
    {
        int ew = sw + size -1;
        int eh = sh + size -1;
                
        if(ew >= board.length || eh>=board[0].length) return false;
        
        for(int r = sw ; r<=ew;r++){
            for(int c = sh; c<=eh;c++){
                if(board[r][c] == 0){
                    return false;
                }
            }
        }
        return true;
    }
}

 

한 변의 길이를 최대치에서 줄여가면서 조건을 만족하는 정사각형이 있는지 확인하는 방식으로 풀었다.

정확성 테스트는 모두 통과 했지만 효율성 테스트에서 모두 시간 초과가 나서 다른 방법을 찾아야 했다.

 

2. Dynamic Programming (All Pass)

 

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        
        int row = board.length;
        int col = board[0].length;
        
        int[][] dp = new int[row][col];
        
        dp[0][0] = board[0][0];
        
        for(int r = 1; r<row;r++)
        {
            dp[r][0] = board[r][0];
        }
        
        for(int c = 1; c<col;c++)
        {
            dp[0][c] = board[0][c];
        }
        
        
        for(int r = 1;r<row;r++)
        {
            for(int c =1; c<col;c++)
            {
                if(board[r][c]!=0){
                dp[r][c] =  Math.min(dp[r-1][c], Math.min(dp[r][c-1],dp[r-1][c-1]))+1;
                }
            }
        }

    
        for(int r = 0; r<row;r++)
        {
            for(int c =0; c<col;c++)
            {
                answer = Math.max(answer,dp[r][c]);
                //System.out.print(dp[r][c]+" ");
            }
            //System.out.println("");
        }
        return answer * answer;
    }
}

첫 번째 열과 행을 board 배열의 값과 동일하게 세팅을 해주고

그 이후에는 왼쪽 , 위쪽 , 대각선 위쪽의 값 중에 가장 작은 값의 +1을 해주어 정사각형의 크기를 만들어 나가면서 풀었다.

 

머릿속으로는 이렇게 하면 되겠지라는 생각이 들었는데 막상 설명하려니 어려운 것 같다..

어떠한 의도를 설명하거나 전달 하는 것도 개발자의 능력이라고 생각되는데 아직 많이 부족한가 보다