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

문제

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

프로그래머스

 

---

 

문제 설명

지민이는 공원에 이미 많은 사람들이 깔아놓은 돗자리를 피해 자신이 가지고 온 돗자리를 깔고 싶습니다. 지민이가 깔 수 있는 돗자리는 정사각형 형태로, 각 돗자리의 한 변 길이는 리스트 mats에 주어집니다. 공원의 현재 자리 배치는 2차원 배열 park로 주어지며, -1은 빈 공간을 나타내고 알파벳은 이미 돗자리가 깔린 자리를 의미합니다.

지민이가 가진 돗자리 중 공원에서 깔 수 있는 가장 큰 돗자리의 한 변 길이를 찾아 반환해야 하며, 깔 수 있는 돗자리가 없는 경우 -1을 반환해야 합니다.

접근 방법

1. 공원 내 최대 정사각형 찾기 (동적 계획법):
   • 공원 내에서 비어 있는 공간 -1로 구성된 가장 큰 정사각형을 찾아야 합니다.
   • 이를 위해 동적 계획법(DP) 배열 dp를 생성하여 각 위치에서 만들 수 있는 정사각형의 최대 크기를 계산합니다.
   • dp[i][j]는 위치 (i, j)를 오른쪽 아래 꼭짓점으로 하는 최대 정사각형의 한 변 길이를 나타냅니다.
   • 점화식: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, 단 park[i][j]가 -1일 경우에만 적용됩니다.
2. 가장 큰 정사각형 크기 추출:
   • maxSize를 사용하여 공원에서 찾은 가장 큰 비어 있는 정사각형의 한 변 길이를 저장합니다.
3. 돗자리 크기 비교:
   • mats 배열을 내림차순으로 정렬하고, maxSize 이하인 가장 큰 돗자리 크기를 탐색하여 반환합니다.
   • 만약 maxSize보다 작은 돗자리가 없다면 -1을 반환합니다.

 

import java.util.*;
class Solution {
    public int solution(int[] mats, String[][] park) {
        int answer = -1;
        int maxSize = 0;
        int[][] dp = new int[park.length][park[0].length];
        
        for(int i=0; i<park.length; i++) {
            for(int j=0; j<park[0].length; j++) {
                if(park[i][j].equals("-1")) {
                    if(i==0 || j==0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
                    }
                    maxSize = Math.max(maxSize, dp[i][j]);
                }
            }
        }
        
        Arrays.sort(mats);
        for(int i=mats.length-1; i>=0; i--) {
            if(mats[i] <= maxSize) return mats[i];
        }
        
        return answer;
    }
}