[프로그래머스] [PCCE 기출문제] 10번 / 공원

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

프로그래머스

공원의 "-1"로 이루어진 빈 공간에 들어갈 수 있는 정사각형 mats 의 최댓값을 구하는 문제.

parks의 정사각형 빈 공간의 최댓값을 구하고 mat <= 최댓값인 것을 반환하는 식으로 처리. 해당 없을 시 -1

 

parks와 동일한 길이로 생성한 int 이중배열에 현 지점기준 왼쪽과 위쪽, 대각선 방향 중 최솟값에 +1 후 Math.max로 최대값을 갱신한 후 mats 의 값들과 비교하였다.

 

public int solution(int[] mats, String[][] park) {
        int maxSize = findMaxSquareSize(park);
        return findBestMatSize(mats, maxSize);
    }

    // 공원에서 만들 수 있는 가장 큰 정사각형의 한 변 길이 찾기 (DP 활용)
    public int findMaxSquareSize(String[][] park) {
        int rows = park.length;
        int cols = park[0].length;
        int[][] dp = new int[rows][cols]; // DP 테이블 (각 위치에서 만들 수 있는 정사각형 크기)
        int maxSize = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if ("-1".equals(park[i][j])) { // 빈 공간이면
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1; // 가장자리에서는 1x1 정사각형 가능
                    } else {
                        // 현 위치에서 위쪽과 왼쪽, 왼쪽 대각선 위 중 최소값을 구하고 +1 한다.
                        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    }
                    maxSize = Math.max(maxSize, dp[i][j]); // 최대 정사각형 크기 갱신
                }
            }
        }
        return maxSize;
    }

    // 가능한 mats 중에서 maxSize 이하이면서 가장 큰 값을 찾기
    public int findBestMatSize(int[] mats, int maxSize) {
        int bestSize = 0;
        for (int mat : mats) {
            if (mat <= maxSize) {
                bestSize = Math.max(bestSize, mat);
            }
        }
        return bestSize == 0 ? -1 : bestSize;
    }