프로그래머스(Java)- 가장 큰 정사각형 찾기

문제 링크

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

실패한 문제 풀이

• 실패한 풀이

이중 for문을 통해서 접근하는 방식을 취하니깐 효율성 테스트를 통과하지 못했다.
checkSize 메소드에서 다시 한번 가로길이를 확인해야 하는 부분에서 큰 시간을 잡아먹는것 같다. 예를들어 1이 연속으로 9개 나왔을때 맨 앞에서 9인것을 알았다면 그 옆은 자연스럽게 8인것을 알아야 한다고 생각한다.

그래서 생각한 것은 bfs, dp 였는데 이전값을 기억한다는 점에서 dp로 접근해야 한다는 생각이 들었다.

• 실패한 코드

import java.util.*;

class Solution
{
    public int solution(int [][]board){
        int answer = 1;
        int maxLen = Math.min(board.length,board[0].length);
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                if(board[i][j]==1){
                    answer = Math.max(answer,checkSize(answer,i,j,board));
                }
                
            }
        }
        
        return answer;
    }
    
    public int checkSize(int answer, int x,int y,int [][] board){
        int cnt = 0; //가로 길이
        for(int i=y; i<board[0].length; i++){
            if(board[x][i]==0){
                break;
            }else{
                cnt++;
            }
        }
        //현재넓이보다 작으면 바로 컷...
        if(answer>=cnt*cnt){
            return -1;
        }
        
        
        //세로 체크
        //가로의 길이가 전체 세로길이보다 크면 시마이...
        if(cnt>board.length-x){
            return -1;
        }
        int idx=x;
        
        for(int i=0; i<cnt; i++){
            if(board[idx++][y]==0){
                return -1;
            }else{
                
            }
        }
        
        //가로 세로가 같다면 전체 체크
        idx=x;
        int idy=y+1;
        for(int i=0; i<cnt-1; i++){
            for(int j=0; j<cnt-1; j++){
                if(board[idx+1][idy++]==0){
                    return -1;
                }
            }
            idx++;
            idy=y+1;
        }
        
        return cnt*cnt;
    }
}

문제 풀이

dp를 이용해서 문제를 해결했다.
board와 같은 크기의 dp 배열을 만들고

0번째 열과, 0번째 행에 있는 모든 값들을 board배열과 동일하게 만들었다.

        for(int i=0; i<board.length; i++){
            dp[i][0] = board[i][0];
            sum+=dp[i][0];
        }
        
        for(int i=0; i<board[0].length; i++){
            dp[0][i]=board[0][i];
            sum+=dp[0][i];
        }

여기서 만약에 1개짜리 정사각형이 있을수도 있기에 초기값을 입력하는 과정에서
dp에 1의 값이 담길때마다 sum이라는 변수에 +1을 해줬다.

        if(sum>0){
            answer=1;
        }

dp[i][j]는 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]과 비교하여
자신이 넓이가 몇인 정사각형의 기준점이 되는지 나타내는 값이다.
예를들어

dp[i-1][j-1]=1 | dp[i-1][j]=1
dp[i][j-1]=1 | dp[i][j] =1
인경우 길이가 2인 정사각형이 되므로 dp[i][j]=4 이다.

ex)

0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0

이라는 board 배열이 있다.
초기 dp값은 아래처럼 입력된다.

0 1 1 1
1 0 0 0
1 0 0 0
0 0 0 0

dp[i][j]에 대해서
1) 기존의 board[i][j]의 값이 0이라면 자신은 정사각형에 포함될수 없으므로
dp[i][j]=0이다.

2) dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 중에 0이 있을경우에는 길이가 1보다 큰 정사각형을 만들수가 없으므로 dp[i][j]=1이다.

3) dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 가 모두 같은 값이면 dp[i][j]를 포함하여 길이가 1이더 긴 정사각형을 만들 수 있다. 그래서 dp[i][j]는 dp[i-1][j-1]의 제곱근의 +1 한값의 제곱이다.

ex) dp[i-1][j-1]=4 이면 실제 dp[i-1][j-1]은 길이가 2인 정사각형이므로 dp[i][j]는 길이가 3인 정사각형이 된다. 그래서 dp[i][j]=9가된다.

4) 나머지 경우는 dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 가 모두 같지는 않지만 0도 아닌경우이다. 이경우에 정사각형의 길이는 가장 짧은 길이 + 1의 값을 가진다.
ex) 1,4,9의 값을 가지고 있는 경우 길이는 가장짧은 1의 값에 +1 한것이 되어 dp[i][j]=4이다.

for(int i=1; i<dp.length;i++){
            for(int j=1; j<dp[0].length; j++){
                
                if(board[i][j]==0){
                    // System.out.println("if문 : "+i+" "+j);
                    dp[i][j]=0;
                }else if(dp[i-1][j-1]==0 || dp[i-1][j]==0 || dp[i][j-1]==0){
                    // System.out.println("else if문1 : "+i+" "+j);
                    dp[i][j]=1;
                     //System.out.println(Arrays.deepToString(dp));
                }else if(dp[i-1][j-1]==dp[i-1][j] && dp[i-1][j]==dp[i][j-1]){
                    // System.out.println("else if문2 : "+i+" "+j);
                    dp[i][j]= ((int)(Math.sqrt(dp[i-1][j-1]))+1 )*((int)(Math.sqrt(dp[i-1][j-1]))+1);
                }else{
                    // System.out.println("else 문 : "+i+" "+j);
                    int min = Math.min(dp[i-1][j-1],dp[i-1][j]);
                    dp[i][j]= (int)(Math.sqrt(Math.min(min,dp[i][j-1])))+1;
                    dp[i][j] = dp[i][j]*dp[i][j];
                    
                }
                answer=Math.max(answer,dp[i][j]);
                //System.out.println(Arrays.deepToString(dp));
            }
            
        }

코드

import java.util.*;

class Solution{
    public int solution(int [][]board){
        int answer = 0;
        int sum = 0;
        int [][] dp = new int[board.length][board[0].length];

        for(int i=0; i<board.length; i++){
            dp[i][0] = board[i][0];
            sum+=dp[i][0];
        }
        
        for(int i=0; i<board[0].length; i++){
            dp[0][i]=board[0][i];
            sum+=dp[0][i];
        }
        
        if(sum>0){
            answer=1;
        }
        
        //System.out.println(Arrays.deepToString(dp));
        for(int i=1; i<dp.length;i++){
            for(int j=1; j<dp[0].length; j++){
                
                if(board[i][j]==0){
                    // System.out.println("if문 : "+i+" "+j);
                    dp[i][j]=0;
                }else if(dp[i-1][j-1]==0 || dp[i-1][j]==0 || dp[i][j-1]==0){
                    // System.out.println("else if문1 : "+i+" "+j);
                    dp[i][j]=1;
                     //System.out.println(Arrays.deepToString(dp));
                }else if(dp[i-1][j-1]==dp[i-1][j] && dp[i-1][j]==dp[i][j-1]){
                    // System.out.println("else if문2 : "+i+" "+j);
                    dp[i][j]= ((int)(Math.sqrt(dp[i-1][j-1]))+1 )*((int)(Math.sqrt(dp[i-1][j-1]))+1);
                }else{
                    // System.out.println("else 문 : "+i+" "+j);
                    int min = Math.min(dp[i-1][j-1],dp[i-1][j]);
                    dp[i][j]= (int)(Math.sqrt(Math.min(min,dp[i][j-1])))+1;
                    dp[i][j] = dp[i][j]*dp[i][j];
                    
                }
                answer=Math.max(answer,dp[i][j]);
                //System.out.println(Arrays.deepToString(dp));
            }
            
        }
        // System.out.println(Arrays.deepToString(dp));


        return answer;
    }
    
    
}