Today's Algorithm(2019-02-07)

programmers. 가장 큰 정사각형 찾기

dp를 이용하는 문제였습니다. 처음엔 하나하나 들러서 갈 수 있는 최대길이를 반복문을 통해 찾아 해결하려고 했었습니다. 그런데 효율성 테스트까지 있는 것보니 이렇게 해서는 복잡도가 커서 통과하지 않을 것 같더라구요. 고민하다 다른 사람의 블로그를 참고하였습니다. 역시나 좀 더 쉽게 해결할 수 있는 방법이 있더라구요. dp 문제는 알고나면 딱 그렇게 푸는게 보이는데 모르는 상태에선 dp문제라는 것을 아직은 감잡기가 힘든 것 같아요.

 

전략은 1일 때 위, 왼쪽, 좌측위 중에서 가장 작은 값에 +1을 해가면서 표시를 해두고 나중에 가장 큰 값을 찾아 제곱하는 것입니다. 처음엔 위, 왼쪽만으로 제대로 계산이 될 줄 알았는데요. 생각해보니 위, 왼쪽이 예를들어 1이 오더라도 좌측위가 0이면 정사각형이 될 수 없더라구요. 그리고 가장 작은 값의 +1하는 전략은 조금만 생각해보면 적어도 가장 작은값 +1 하는 값은 나올 수 있기 때문에 가능한 것입니다. 예를들어 (1, 0, 1)이 있을 때는 그 점이 원래 1이기 때문에 가장 작은 값(0) + 1은 원값을 보존할 수 있습니다. 또 (2, 1, 2)일 경우는 적어도 가장 작은 값(1) + 1, 즉 4인 정사각형은 그릴 수 있기 때문에 가능합니다.

 

이를 코드로 옯겨보면 다음과 같습니다.

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

        for (int row = 1; row < board.length; row++) {
            for (int col = 1; col < board[row].length; col++) {
                int temp = board[row][col];
                if (temp == 0) continue;
                board[row][col] = getValue(board, row, col);
            }
        }

        for (int[] ints : board) {
            for (int anInt : ints) {
                answer = Math.max(anInt, answer);
            }
        }

        return (int) Math.pow(answer, 2);
    }

    public int getValue(int[][] board, int row, int col) {
        return Math.min(Math.min(board[row][col - 1], board[row - 1][col - 1]), board[row - 1][col]) + 1;
    }
}

인덱스가 1부터 시작하는 이유는 row 또는 col이 0인 경우는 어차피 자기보다 큰 정사각형을 못 만드는 조건이기 때문입니다. 그리고 주의할 점은 0인 경우와 1인 경우가 있다는 것인데요.

• 0인 경우 : 모든 수가 0인 경우
• 1인 경우 : 하나의 정사각형도 구성되지 않는 경우

 

처음에 코드를 구현하고 테스트 케이스 1개가 자꾸 통과가 안되었는데요. 그건 row 또는 col이 0인 부분에 1이 있어서 그런것 같습니다. 이 값은 dp반복문 돌때 체크를 안하는 부분이기 때문에 이후 따로 반복문을 돌며 가장 큰 값을 찾아서 해결할 수 있었습니다.