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

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DP

. 입력받은 2차원 배열의 행이나 열의 크기가 1이라면 바로 1을 출력하고 종료하게 한다. (예외처리, TC 1)

. 그게 아니라면, 2차원 배열을 (왼쪽 위 vs 왼쪽 vs 위쪽) 세 칸中 가장 작은 값 + 1을 해 갱신한다.

. 새롭게 완성된 2차원 배열에서 최댓값을 찾아 출력한다.

 

- dp 배열의 의미 : 현재 칸 (i, j)까지의 가장 긴 정사각형 길이 (여기서는 그냥 입력받은 2차원 배열 그대로 활용)

- dp 점화식 :  (왼쪽, 위, 왼쪽 위) 세 칸 中 최솟값 + 1

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    public int solution(int[][] board) {
        int answer = 0;
        int r = board.length;
        int c = board[0].length;
        
        // board의 행 또는 열이 1인 경우 예외처리
        if(r < 2 || c < 2) {
            return 1;
        }
            
        for(int i = 1 ; i < r ; i++) {
            for(int j = 1 ; j < c ; j++) {
                if(board[i][j] == 0)    continue;
            
                // (왼쪽 위 vs 왼쪽 vs 위쪽) 세 칸 중 가장 작은 값 + 1을 해 채운다.
                board[i][j] = Math.min(board[i-1][j-1], Math.min(board[i-1][j], board[i][j - 1])) + 1;
                answer = Math.max(answer, board[i][j]);
            }
        }
        
        return answer*answer;
    }
}

 

 

---

💦 어려웠던 점

- 브루트포스로 풀려다가 장렬하게 전사했다.. 이런 문제는 dp문제라는 걸 바로 간파했어야 했는디,,

- 2차원 누적합 문제 점화식으로 풀어봤는데,, 이 문제는 칸의 숫자값을 모두 더하는 누적합 문제가 아니라 그냥 (왼쪽, 위, 왼쪽 위) 세 칸 中 제일 작은 값 + 1해서 정사각형 길이를 구하면 되는 문제였던 더 쉬운 편이었던 것이다,,

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Java] 프로그래머스 Lv.2 : 가장 큰 정사각형 찾기

 

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