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

문제내용

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

---

문제풀이

처음엔 1이 연속되는 길이를 구하고 각 행을 탐색하며 같은 위치에 구했던 길이만큼 1이 연속되는지 확인하는 식으로 구현했다. 근데 이렇게 해버리면 최악의 경우 O(N^4)가 발생하기 때문에 시간이 굉장히 오래걸리게 된다.

따라서 DP를 이용해 문제를 풀어야한다.

 

다른 블로그를 보면 설명이 자세히 나와있는데 간단히 설명하자면

좌상단 -> 우하단으로 탐색하며 각 인덱스의 위치에서 이전 값을 통해 최대 길이가 몇인지 알아내는 방법이다.

1	1	1
1	2	2
1	2	3

표를 보면 (1,1)에선 최대 길이 2의 사각형을 만들수 있다. 즉, board 배열에서 (0,0) (0,1) (1,0) (1,1) 이 1이라는 의미다.

이를 위해 Min = (dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1]) + 1 을 이용해 각 인덱스의 값을 구해준다.

(현재값 기준으로 상단, 좌측, 좌상단 의 값을 비교)

 

코드를 보고 생각하자.

---

코드

public class Solution {
    public int solution(int[][] board){
        int[][] dp = new int[board.length][board[0].length];
        
        //첫 행,열을 복사
        //기준값이 필요.
        for(int i=0; i<board.length; i++) {
        	dp[i][0] = board[i][0];
        }
        for(int j=0; j<board[0].length; j++) {
        	dp[0][j] = board[0][j];
        }
        
        //1번 인덱스부터 채우기.
        for(int i=1; i<dp.length; i++) {
        	for(int j=1; j<dp[0].length; j++) {
        		if(board[i][j]!=1) continue;//0이라면 dp 갱신할 필요 없음.
        		int min = Math.min(dp[i-1][j], dp[i][j-1]);
        		min = Math.min(min,dp[i-1][j-1]);
        		dp[i][j] = min+1;
        	}
        }
        
        int max = -1;
        //최댓값 찾기
        for(int i=0; i<dp.length; i++) {
        	for(int j=0; j<dp[0].length; j++) {
        		max = Math.max(max, dp[i][j]*dp[i][j]);
        	}
        }
      
        return max;
    }
}

---

마치며

처음엔 쉬워 보였지만 풀수록 어려웠던 문제다.. DP는 언제나 어려운듯ㅠ