[Programmers] PCCE 기출문제 10번 - 공원 - Java

문제

프로그래머스

 

풀이

돗자리가 깔려있지 않은 구역에서 최대 정사각형의 길이를 구해서, mat에서 최대 길이 이하의 값을 가지는 돗자리 길이 중 최댓값을 구하는 문제이다.

 

필자는 이 문제에서 어떤 영역의 최대 영역을 구할때, dp를 이용해서 최대 길이를 구할 수 있다고 생각했다.

 

1. dp에서 어렵게 만드는 것은 어떤 점에 해당하는 최대 정사각형의 길이를 구하는 것이다.

 

2. 테이블을 정의

dp[i][j] = (i, j)를 정사각형 우측 하단의 점일때, 가질 수 있는 정사각형 길이

 

3. 원하는 답을 낼 수 있는지 파악해본다.

dp를 전부 순회하면서 가지는 최댓값이 돗자리를 펼 수 있는 최대 길이다.

answer = max(dp[i][j], answer);

 

4. 정의한 테이블을 어떻게 초기화할지 생각한다.

이 문제 조건에서 길이가 1인 정사각형이 나올 수 있으므로, 가로 세로 길이를 + 1씩 더해서, 배열을 생성하고,

이미 펴져 있는 돗자리는 0으로 초기화 했으므로, 초기화는 되어있다.

 

5. 점화식을 도출해본다.

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1이다.

생각을 해보면 현재 점에서 대각 왼쪽 위쪽에서 길이중에, 가장 작은 값에서 + 1을 더한 값이 (i, j)에서 가질 수 있는 정사각형의 길이이다.

1 1

2 x

라고 치면, 왼쪽에 있는 점은 길이가 2인 정사각형을 가지고 있고, 대각, 위쪽은 1인 정사각형을 가질 수 있다.

그러면 당연히 x도 정사각형 길이가 1이다.

 

2 2

2 x

라고 하면, 왼쪽, 대각, 위쪽은 모두 길이가 2인 정사각형이 될 수 있으므로, x는 3이 된다.

 

6. 최대 정사각형의 길이 이하 중 최댓값을 가지는 매트의 길이를 찾는다.

소스코드

import java.util.Arrays;

class Solution {
    public int solution(int[] mats, String[][] park) {
        int[][] dp = new int[park.length + 1][park[0].length + 1];
        
        for (int i = 1; i < park.length + 1; i++) {
            for (int j = 1; j < park[0].length + 1; j++) {
                if (park[i - 1][j - 1].equals("-1")) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        
        int max = Integer.MIN_VALUE;
        
        for (int i = 1; i < park.length + 1; i++) {
            for (int j = 1; j < park[0].length + 1; j++) {    
                if (dp[i][j] > 0) {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        
        int answer = -1;
        
        for (int m : mats) {
            if (m <= max) {
                answer = Math.max(answer, m);
            }
        }
        
        return answer;
    }
}

 

실행결과