가장 큰 정사각형 찾기 [자바]

 

🧫 문제 분석

✔️ 출처

가장 큰 정사각형 찾기 level 2

📖 문제

 

2번 시도후 푼 문제다.

 

1차 시도 

정 사각형을 찾는게 문제인데 

처음에는 1차원 배열에 각 열에 대한 개수를 세서

최솟값을 갱신하면서 카운트를 하고

최솟값과 카운트 값이 같다면 가장 큰 정사각형 후보로 넣는 식이였다.

당연히 틀렸고, 시간초과났다.

 

 

2차 시도

문득 생각해보니 DP에 대해 배웠을 때 

값을 누적하고 원하는 부분의 값을 얻는 방법이 떠올랐다.

dp[i][j] - dp[i-1][j] - dp[i][j] + dp[i-1][j-1]

 

여기에 정사각형 한 변의 길이를 더해주고 영역 값을 구한 뒤 

 정사각형 넓이 == 영역 값  ? 한 변 길이 + 1 , 정사각형 넓이 최신화 

 

이런식으로 하면 되지 않을까 라는 생각에 해봤는데 성공했다.

 

정사각형 한 변의 길이가 점점 늘어나는 방식이기에 2중 배열이여도 금방 끝난다. 

 

물론 더 좋은 정석적인 방법이 있다. 

나도 그걸 배워볼려고 한다. 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    public int solution(int[][] board) {
        int answer = 0;
        
        int[][] dp = new int[board.length + 1][board[0].length + 1];
        
        // 누적값 저장
        for (int i = 1; i <= board.length; i++) {
            for (int j = 1; j <= board[0].length; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + board[i - 1][j - 1] - dp[i - 1][j - 1];
            }
        }
        
        
        int size = 0;
        int rightValue = (size + 1) * (size + 1); // 정사각형 안에 존재하는 1의 개수
        boolean flag = false; // 0일 경우 대비
        
        // 처음부터 탐색
        // 사각형 모양 찾기 
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                
                while (i + size < dp.length 
                       && j + size < dp[0].length) {
                    
                    int result = dp[i + size][j + size] - dp[i - 1][j + size] - dp[i + size][j - 1] + (dp[i-1][j-1]);    
                    
                    // 정사각형이 아니면 다음 위치에서 탐색
                    if (result != rightValue) break;
                    
                    size++; // 다음 탐색 사각형 사이즈 증가 
                    flag = true; 
                    rightValue = (size + 1) * (size + 1);
                }
            }
        }
        
        return flag ? (size * size) : 0;
    }
}

flag는 0일 경우를 생각했는데 문제에서 없는 경우를 주지않았으므로 항상 답이 있는 것 같다. 

flag는 빼도 된다. 

 

🔅 다른 사람 코드 이해해보기

1	1	1
1	1	1
1	1	1

 

 정사각형의 조건은 무엇인가? 

 

2*2  정사각형의 경우를 생각해보자

 

현재 자신의 위치 값과 좌, 왼쪽상단, 상에 위치한 값이 1이면 정사각형이 된다. 

 3*3도 마찬가지다. 

좌, 우측상단, 상이 2*2이면 된다. 

 

이런식으로 정사각형을 구별해낼 수 있다. 

 

 

class Solution{
    public int solution(int [][]board) {
        int answer = 0;
        boolean flag = false; // 1*1 로 주어질 경우 대처
        
        for (int i = 1; i < board.length; i++) {
            flag = true;
            
            for (int j = 1; j < board[0].length; j++) {
                if (board[i][j] > 0) {
                    board[i][j] = Math.min(Math.min(board[i - 1][j], board[i][j-1]), board[i-1][j-1]) + 1;
                    
                    answer = Math.max(board[i][j], answer);
                }
            }
        }
        
        return flag ? answer * answer : 1;
    }
}

 

 

효율성 테스트에서 거의 2배 더 빠른 것을 확인할 수 있다.

 

 

❗ 오답노트 / 필요한 지식

1. 이번에 배운 것을 잘 기억하자.