[코딩테스트] 프로그래머스 - 가장 큰 정사각형 찾기(Java)

🍪 설명

레벨: 2
언어: Java

🍩 느낀점

처음에 해당문제 대해 알고리즘에 대해 고민을 했었다..
BFS 방법을 생각해내긴 했지만 정말 이방법이 맞을까? 좀더 효율적인 방법이 있을까?? 타인의 도움이 필요한다고 생각해서 검색을 해봤는데 해당문제는 DP로 접근해서 풀어야 된다고 말이 나와있더라..
DP 알고리즘에 대한 개념은 이해하고 있지만 문제는 처음 접해봐서 어떻게 해야되는지 참고하고 풀이방법에 대해 생각을 해봤는데..

내가 생각해낸 풀이방법은
1. board 배열을 루프로 돌리는데
2. 왼쪽 모서리면과 상단 모서리면은 값이 1이여도 추가로 외곽값이 없으니 무조건 정사각형 크기가 1일수 밖에없다고 생각하였고,
3. 우측, 하단으로 내려가면서 이전 좌측, 상단, 좌측상단에 있는 만들수있는 크기를 넣어둔 DP배열변수에서 꺼내까지고 만들수있는 정사각형이 최소값으로 나타내져 +1을 하는방식으로 정사각형 크기를 반환

이런방식으로 풀었습니다..

가장 좋아요 많이 받은 코드는
2018년도 댓글이 달린것보니 아주 예전방식이 나의 코드 차이점은..
루프 두번돈걸 한번 돌게 만든것 차이정도가 있고 알고리즘은 결국 DP 방식입니다..

🌰 내가 작성한 코드

class Solution
{
    public int solution(int [][]board)
    {
        int[][] dp = new int[board.length][board[0].length];
        
        int answer = 0;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                int value = board[i][j];
                if(value == 0) continue;
                
                dp[i][j] = (i == 0 || j == 0) 
                    ? value
                    : Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                
                answer = Math.max(answer, dp[i][j]);
            }
        }
        

        return answer * answer;
    }
}

🥭 가장 좋아요 많이 받은코드

// 문제가 개편되었습니다. 이로 인해 함수 구성이나 테스트케이스가 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.
// 새로운 함수 구성을 적용하려면 [코드 초기화] 버튼을 누르세요. 단, [코드 초기화] 버튼을 누르면 작성 중인 코드는 사라집니다.
class TryHelloWorld
{
    public int findLargestSquare(char [][]board)
    {
       int answer = 0;
        int[][] aa = new int[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] == 'O' ) {
                    aa[i][j] = 1;
                } else {
                    aa[i][j] = 0;
                }
            }
        }

        for(int i=1;i<aa.length;i++) {
            for(int j=1;j<aa[i].length;j++) {
                if( aa[i][j] == 1 ) {
                    int minVal = 0;
                    minVal = aa[i-1][j] < aa[i][j-1] ? aa[i-1][j] : aa[i][j-1];
                    minVal = aa[i-1][j-1] < minVal ? aa[i-1][j-1] : minVal;

                    aa[i][j] = minVal + 1;
                    answer = answer < aa[i][j] ? aa[i][j] : answer;
                }
            }
        }



        return answer*answer;
    }
    public static void main(String[] args)
    {
        TryHelloWorld test = new TryHelloWorld();
                char [][]board ={
                {'X','O','O','O','X'},
                {'X','O','O','O','O'},
                {'X','X','O','O','O'},
                {'X','X','O','O','O'},
                {'X','X','X','X','X'}};

        System.out.println(test.findLargestSquare(board));
    }
}