Menu

Subscribe

[JAVA/프로그래머스] 연습문제: 가장 큰 정사각형 찾기

HEESOO on Programmers

👀 문제

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

👊 도전

1. 설계

  1. (i, j)가 정사각형이 되기 위해서, 내 왼쪽(i, j-1), 내 위쪽(i-1, j), 내 대각선 앞(i-1, j-1)이 같은 값을 가져야 한다.
  2. 이를 이용하여 점화식을 구현한다.

2. 구현

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

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution
{
    public int solution(int [][]board)
    {
        int answer=0;
        // 새 배열의 사이즈
        int n=board.length+1;
        int m=board[0].length+1;
        int[][] map=new int[n][m];
        
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                map[i][j]=board[i-1][j-1]; // 값 복사
            }
        }

        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(map[i][j]==1){
                    map[i][j]=Math.min(map[i][j-1], Math.min(map[i-1][j], map[i-1][j-1]))+1;
                    answer=Math.max(answer, map[i][j]);
                }
            }
        }
        return answer*answer;
    }
}

3. 결과

실행결과 🤟 성공 🤟
input이 1000이지만 혹시나 하는 마음에 BFS로 구현하였는데 몇몇 케이스 실패에 시간 초과가 발생했다. 일단 범위가 크면 DP 점화식을 생각해봐야 겠다.

4. 설명

  1. (i, j)가 정사각형이 되기 위한 조건을 생각한다
    • (i, j)가 정사각형이 되려면 값이 1이어야 한다.
    • 다음으로, 내 주변이 0이 아니어야 한다.
    • 위에서부터 순차 탐색한다면, 이미 체크한 인덱스들 중 내 주변인 왼쪽(i, j-1), 위(i-1, j), 대각선 위(i-1, j-1)가 된다.
    • 세 값이 같은 값을 가져야 나 포함해서 정사각형이 커질(될) 수 있다.
    • 따라서 세 값 중 하나+1(내가 포함되어 정사각형이 커졌으므로)를 저장한다.
    • 참고로, 배열에는 정사각형의 길이를 저장한다.
    • 세 값이 다르다면, 셋 중 제일 작은 값+1을 저장한다. 그 값이 현재까지 만들어진 정사각형의 길이이기 때문이다.
    • 따라서, 세 값을 비교하기 위해 인덱스 에러가 뜨지 않도록 배열의 맨 왼쪽과 위에 행열을 하나 더 붙인 map을 만들고, 값을 복사한 후 이를 사용한다.

👏 해결 완료!

다른 사람들의 풀이 중에 board의 크기를 늘리지 않고 (1,1)부터 체크하는 코드가 있다. 이 경우 board의 0행, 0열은 체크하지 않기 때문에 여기를 포함하는 정사각형의 경우에는 잘못된 값을 낸다. 테스트케이스에서는 이와 같은 입력값이 없는지 성공이 뜨지만, 해당 input까지 생각한다면 배열을 늘리는 것이 낫다.

참고