[프로그래머스] Level 2 가장 큰 정사각형 찾기 (JAVA)

문제

---

풀이

for문 여러개 중첩해서 풀었더니 정답은 나왔지만 효율성은 0점을 맞았다ㅎㅎ
효율성 검사가 있으니 DP 문제겠거니 싶어서 DP로 생각해서 풀려고 노력했다. 하지만 DP 문제플 푼지 너무 오래된 탓인지 풀리지 않았다! 그래서 구글링을 통해 답을 얻을 수 있었다.

1. extendBoard(): 인덱스 검색의 용이함을 위해 board의 좌상단에 패딩을 더해준다.
2. 좌상단부터 우하단까지 차례로 탐색한다.
   • 본인이 0이 아닌 경우에만 정사각형을 추가로 확장할 수 있다.
   • 위, 왼쪽, 그리고 좌측 대각선의 값 중 최솟값이 확장 가능한 정사각형의 개수다.
   • 본인을 포함해서 정사각형의 크기를 키워야 하기 때문에 1을 더한 값으로 newBoard[i][j]를 갱신한다.
   • 최종 결과값인 maxSize를 최댓값으로 갱신한다.

---

코드

class Solution {       
    public int solution(int[][] board) {
        int[][] newBoard = extendBoard(board);
        int maxSize = 0;
        for (int i = 1; i < newBoard.length; i++)
            for (int j = 1; j < newBoard[0].length; j++)
                if (newBoard[i][j] != 0) {
                    newBoard[i][j] = Math.min(Math.min(newBoard[i - 1][j], newBoard[i - 1][j - 1]), newBoard[i][j - 1]) + 1;
                    maxSize = Math.max(maxSize, newBoard[i][j]);
                }
        return (int) Math.pow(maxSize, 2);
    }

    private int[][] extendBoard(int[][] board) {
        int[][] newBoard = new int[board.length + 1][board[0].length + 1];
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                newBoard[i + 1][j + 1] = board[i][j];
        return newBoard;
    }
}

---

참고

[프로그래머스] 가장 큰 정사각형 찾기