본문 바로가기

Programmers/Level2

가장 큰 정사각형 찾기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        int max = 0;
        // 1행, 1열 체크
        for (int i = 0; i < board.length; i++) {
            if (board[i][0== 1 || board[0][i] == 1) {
                max = 1;
                break;
            }
        }
        for (int i = 1; i < board.length; i++) {
            for (int j = 1; j < board[0].length; j++) {
                // 왼쪽, 왼쪽 위, 위쪽 최솟 값 비교
                if (board[i][j] == 1) {
                    int min = Math.min(Math.min(board[i - 1][j], board[i - 1][j - 1]), board[i][j - 1]);
                    board[i][j] = min + 1;
                    max = Math.max(max, board[i][j]);
                }
            }
        }
        answer = max * max;
 
        return answer;
    }
}
cs

현재 값이 1일 때 왼쪽, 왼쪽 위, 위쪽을 비교하여 최솟값 + 1 을 반환한다.

만약 모두 1일 경우 2 * 2 정사각형이 만들어지므로 현재 값은 2가 된다.

모두 2일 경우에는 마찬가지로 3 * 3 정사각형이 만들어진다.

최종 max를 구한 후 제곱하여 answer를 반환하였다.

 

참고 사이트 : https://zzang9ha.tistory.com/189

'Programmers > Level2' 카테고리의 다른 글

구명보트  (0) 2021.07.26
영어 끝말잇기  (0) 2021.07.25
[1차] 캐시  (0) 2021.07.24
삼각 달팽이  (0) 2021.07.24
다리를 지나는 트럭  (0) 2021.07.23