Lv 2. 가장 큰 정사각형

 

오늘은 별첨으로 다른코드도 있다.
DP라는 다이나믹프로그래밍이 가로 ,세로 나눌것이아니라 한꺼번에 해도 된다는 생각을 왜 못했을까
시간이 너무오래걸렸다. 간단히 짤수 있는 코드임에도 불구하고..

주석은 내가 고민한 흔적이며
첫 코드는 DP로 가로 세로 이차원배열을 만들어  대각선 루프를 돌며 비교한것이고
두번째 코드는 가로 세로 대각선을 한꺼번에 비교한 코드이다.

당연히 두번째코드가 3배정도 훨씬 더 빠르다.
조금더 고민해보자..항상 생각하고 보다 쉽게 효율적이게 간단하게 짤수 있게 노력하자.

// 가장 큰 정사각형 찾기
// 가장 큰 정사각형을 찾는다라...
// 1 1 0 0 1 
// 1 0 1 1 1
// 0 0 1 1 1 
// 0 1 1 1 1
// 0 1 1 1 1 
// 1000 * 1000 = 1.000.000  백만인데.. 백만칸을 싹다 돌면서한다..? 미친짓

// DP?  
// 1 2 0 0 1
// 1 0 1 2 3
// 0 1 2 3 4
// 1 2 0 1 2 
// 0 1 2 3 4
// 0 1 2 3 4

// 세로로 DP   // 가로로 DP   //대각선 DP 실제 구현해서 +1 하면서 하기 
// 1 1 0 0 1  // 1 2 0 0 1
// 2 0 1 1 2  // 1 0 1 2 3
// 0 0 2 2 3  // 0 1 2 3 4
// 1 1 3 3 4  // 1 2 3 4 5
// 0 2 4 4 5  // 0 1 2 3 4
// 0 3 5 5 6  // 0 1 2 3 4 

// 1 2 3 4 5 6 7 8
// 1 2 3 0 4 5 6 7
// 1 2 3 4 5 0 1 2
// 1 0 1 2 3 4 5 0
// 1 2 3 4 5 6 0 1
// 1 2 3 4 5 6 7 8
// 1 0 1 2 3 4 5 6
// 1 2 3 4 5 6 7 8

// 1 1 1 1 1 1 1 1
// 2 2 2 0 2 2 2 2
// 3 3 3 1 3 0 1 2
// 4 0 4 2 4 1 2 0
// 5 1 5 3 5 2 0 1
// 6 2 6 4 6 3 1 2
// 7 0 7 5 7 4 2 3
// 8 1 8 6 8 5 3 4
// 요고네 요거 

// Max 최신화 max 보다 낮은거 확인 ㄴㄴ 
// max 보다 높은데 내리면서 낮추다가 max보다 낮으면 확인 ㄴㄴ

// 백만칸 다돌면서 dp[][] 배열 생성

// 앞에서 뒤로 하는게 편하긴한데 글케하자.
// 백만칸중에 확인 안하는거 다수
// 확인하더라도 한줄만 확인 쭉하면된다.


import java.util.*;

class Solution
{
    int[][] dp1,dp2;
    int max = Integer.MIN_VALUE;
    
    //dp array create method
    //가로 dp1 세로 dp2 배열 생성
    public void createDp(int x, int y, int[][] board){
        int dsum = 0 , psum = 0; //가로 dsum 세로 psum
        for(int i = 0 ; i < x ; i++){
            for(int j = 0 ; j < y ; j++){
                if(board[i][j] == 0)
                    dsum = 0;
                else
                    dsum++;
                dp1[i][j] = dsum;
            }
        }
        for(int i = 0 ; i < y ; i++){
            for(int j = 0 ; j < x ; j++){
                if(board[j][i] == 0)
                    psum = 0;
                else
                    psum++;
                dp2[j][i] = psum;
            }
        }
    }
    // DP check method
    // 대각선 체크 
    public void dpCheck(int x, int y, int[][] board){
        int sum = 1;
        for (int k = 0; k < x + y - 1; k++) {
            int iStart = (k < y) ? 0 : k - y + 1;
            int jStart = (k < y) ? k : y - 1;

            int i = iStart;
            int j = jStart;

            // 대각선 순회
            while (i < x && j >= 0) {
                if(board[i][j] == 0){ //0이면 continue;
                    sum = 0;
                    continue;
                }
                else{
                    if(i - 1 >= 0 && j - 1 >= 0){ //범위 안일때
                        if(sum <= dp1[i][j-1] && sum <= dp2[i-1][j])
                            sum++;
                        else
                            sum = Math.max(dp1[i][j-1],dp2[i-1][j]);
                    }
                }
                max = max < sum ? sum : max; //max 최신화
                i++;
                j--;
            }
        }
    }
    
    public int solution(int [][]board)
    {
        int x = board.length;
        int y = board[0].length;
        dp1 = new int[x][y];
        dp2 = new int[x][y];
        createDp(x,y,board);
        dpCheck(x,y,board);
        return max*max;
    }
}

import java.util.*;

class Solution {
    public int solution(int [][]board) {
        int n = board.length;
        int m = board[0].length;
        
        int[][] dp = new int[n][m];
        int maxSquareLength = 0;

        // DP 배열 초기화 및 정사각형 계산
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1) {
                    // 경계선에 있는 경우에는 자기 자신이 정사각형의 한 변 길이
                    if (i == 0 || j == 0) {
                        dp[i][j] = board[i][j];
                    } else {
                        // 상단, 좌측, 대각선 상단-좌측 값을 참조
                        dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                    }
                    // 가장 큰 정사각형의 한 변의 길이 갱신
                    maxSquareLength = Math.max(maxSquareLength, dp[i][j]);
                }
            }
        }

        // 가장 큰 정사각형의 면적 반환
        return maxSquareLength * maxSquareLength;
    }
}