문제

https://programmers.co.kr/learn/courses/18/lessons/1879

코드

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public int solution(int[][] board) {

    if (board.length < 2 || board[0].length < 2) {
        return smallSquare(board);
    }

    int answer = nomalSquare(board);
    return answer * answer;
}

private int smallSquare(int[][] board) {
    int size = 0;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == 1) {
                size = 1;
                break;
            }
        }

        if (size == 1) {
            break;
        }
    }

    return size;
}

private int nomalSquare(int[][] board) {
    int answer = 0;

    int min = Integer.MAX_VALUE;
    for (int i = 1; i < board.length; i++) {
        for (int j = 1; j < board[0].length; j++) {
            if (board[i][j] == 0) {
                continue;
            }

            board[i][j] = Math.min(board[i-1][j-1], Math.min(board[i-1][j], board[i][j-1])) + 1;

            if (board[i][j] > answer) {
                answer = board[i][j];
            }
        }
    }

    return answer;
}

흐름

  1. 배열의 크기가 2보다 작은 경우엔 크기가 1인 정사각형 밖에 존재 할 수 없으므로, 배열의 크키가 2 이하인 배열에 1이 들어있는지 확인
  2. 배열을 [1,1] 부터 반복
  3. 현재 위치의 값이 0인 경우엔 절대 정사각형 일 수 없으므로 더 이상 돌지 않고 continue
  4. 현재 위치(1,1)의 좌상(0,0)과 상(0,1) 좌(1,0)의 값들중 최소값을 구함
  5. 구한 최소값에 1을 더해서 현재 위치에 할당
  6. 구한 최소값이 현재 가장 큰 정사각형의 크기 보다 크면 정사각형의 크기를 구한 최소값으로 변경
  7. 반복
  8. 끝

흐름 이미지 설명

사각형

결과

정확성 테스트

번호 속도
테스트 1 통과 (0.86ms, 52.4MB)
테스트 2 통과 (0.77ms, 52.2MB)
테스트 3 통과 (0.83ms, 52.6MB)
테스트 4 통과 (0.75ms, 50.4MB)
테스트 5 통과 (0.72ms, 52.8MB)
테스트 6 통과 (0.83ms, 52.7MB)
테스트 7 통과 (0.79ms, 50.4MB)
테스트 8 통과 (0.83ms, 54.1MB)
테스트 9 통과 (0.79ms, 52.4MB)
테스트 10 통과 (0.83ms, 52.3MB)
테스트 11 통과 (0.75ms, 52.2MB)
테스트 12 통과 (0.79ms, 52.3MB)
테스트 13 통과 (0.76ms, 52.1MB)
테스트 14 통과 (0.83ms, 49.9MB)
테스트 15 통과 (0.75ms, 50.5MB)
테스트 16 통과 (0.91ms, 50MB)
테스트 17 통과 (0.83ms, 52.4MB)
테스트 18 통과 (0.92ms, 52.3MB)
테스트 19 통과 (1.06ms, 52MB)

효율성 테스트

번호 속도
테스트 1 통과 (24.74ms, 97.5MB)
테스트 2 통과 (25.24ms, 99.6MB)
테스트 3 통과 (26.48ms, 99.8MB)

테스트 케이스

1
2
3
assertEquals(9, test.solution(new int[][]{{0,1,1,1} ,{1,1,1,1},{1,1,1,1},{0,0,1,0}}));
assertEquals(4, test.solution(new int[][]{{0,0,1,1} ,{1,1,1,1}}));
assertEquals(1, test.solution(new int[][]{{0,0,1,1}}));

참고 사이트