[programmers] 가장 큰 정사각형 찾기(Java)

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
예를 들어

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

입출력 예

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

작성 코드

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        int row = board.length;
        int col = board[0].length;
        
        int[][] map = new int[row + 1][col + 1];
        
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                if(board[i-1][j-1] != 0){
                    map[i][j] = Math.min(map[i][j - 1], Math.min(map[i - 1][j], map[i - 1][j - 1])) + 1;
                    answer = Math.max(answer, map[i][j]);
                }
            }
        }
        
        return answer * answer;
    }
}

정확성 : 59.6
효율성 : 40.4

DP(Dynamic Programing)를 요구하는 문제이다.

DP의 설명은 아래 포스팅을 참고하면 된다.(추후 추가)

 

코드를 풀이하자면 아래와 같다.

3x3라는 가정을 해봤을 때.

임의로 만든 배열은 (col+1, row+1)이므로

위와 같이 된다. 주어진 배열의 넓이는 2*2로 4가 된다.

코드의 for문을 따라가보면

i = 1, j = 1

i = 1, j = 1

주어진 배열의 값이 0이므로 임의로 만든 배열에 변화는 없다.

answer = 0

i = 1, j = 2

i = 1, j = 2

주어진 배열이 0이 아니므로, 임의로 만든 배열의 값은 북,서,북서쪽 칸의 최솟값의 +1 을한다.

answer = 1

i = 1, j = 3

i = 1, j = 3

주어진 배열의 값이 0이므로 임의로 만든 배열에 변화는 없다.

answer = 1

i = 2, j = 1

i = 2, j = 1

주어진 배열이 0이 아니므로, 임의로 만든 배열의 값은 북,서,북서쪽 칸의 최솟값의 +1 을한다.

answer = 1

i = 2, j = 2

i = 2, j = 2

주어진 배열이 0이 아니므로, 임의로 만든 배열의 값은 북,서,북서쪽 칸의 최솟값의 +1 을한다.

answer = 1

i = 2, j = 3

i = 2, j = 3

주어진 배열의 값이 0이므로 임의로 만든 배열에 변화는 없다.

answer = 1

i = 3, j = 1

i = 3, j = 1

주어진 배열이 0이 아니므로, 임의로 만든 배열의 값은 북,서,북서쪽 칸의 최솟값의 +1 을한다.

answer = 1

i = 3, j = 2

i = 3, j = 2

주어진 배열이 0이 아니므로, 임의로 만든 배열의 값은 북,서,북서쪽 칸의 최솟값의 +1 을한다.

answer = 2

i = 3, j = 3

i = 3, j = 3

주어진 배열의 값이 0이므로 임의로 만든 배열에 변화는 없다.

answer = 2

임의로 만든 배열의 max값의 제곱이 넓이가 된다.

 

이번 문제를 풀면서 내가 정말 부족하다고 느꼈다..

하나하나 포문을 돌려가며 비교하려고 했던것에 자책을 많이 했던거 같다.(처음에 짠 코드는 포문이 많았다.)

결국 문제해설을 보고 혼자 다시 코딩을 하여 답을 도출해낼 수 있었다.

DP관련문제를 몇개정도 더 풀고나면 이런 이론이 정립되겠지라는 생각으로.. 좀더 공부해야 할 것 같다..😥

역시 코딩은 배워도 배워도 끝이 없구나 ㅠ,....

 

포스팅에 오류가 있거나 오타가 있거나 더 효율이 높은 코드를 알고 계신분은 댓글로 알려주시기 바랍니다.

도움이 되셨다면 공감버튼을 눌러주세요.🥰