[PCCP 기출 10번] 공원

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

프로그래머스

 

문제 유형

• 구현

 

문제 난이도

• Lev1

 

문제 분석

해당 문제는 2차원 배열로 이루어진 공원에서 빈 공간에 정사각형 모양의 돗자리를 깐다고 했을 때 깔 수 있는 최대의 한 변의 길이를 구하는 문제이다.

문제에서 park의 길이 <= 50, 돗자리의 길이 <= 10이기 때문에, 완전 탐색을 진행해도 시간 초과 없이 해결할 수 있는 문제였다.
만약 해당 문제를 조금 더 복잡하게 풀고 싶다면, 슬라이딩 윈도우를 사용하면 시간 복잡도와 메모리 효율을 높일 수 있을 것이다.

그러나, 굳이 쉬운 문제를 어렵게 풀 이유는 없을 것 같다.

전체 코드에 주석으로 설명을 추가하였다.

 

전체 코드

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[] mats, String[][] park) {
        int answer = -1;
        
        // 돗자리의 크기를 오름차순 정렬
        Arrays.sort(mats);
        
        // 돗자리의 크기가 큰 순서대로 비교를 시작한다.
        for(int k = mats.length-1; k >= 0; k--) {
        	// 현재 돗자리의 크기
            int n = mats[k];
            
            // 공원을 순회한다.
            for(int i = 0; i <= park.length - n; i++) {
               for(int j = 0; j <= park[0].length - n; j++) {
                   
                   // 돗자리 크기만큼 순회를 돌았을 때, 모두 빈 공간인 경우, false
                   boolean flag = false;

                   label: for(int l = i; l < i + n; l++) {
                       for(int m = j; m < j + n; m++) {
                       	// 빈 공간이 아니라면
                           if (!park[l][m].equals("-1")) {

                               flag = true;
                               break label;
                            }
                       }
                   }
                   
                   if(!flag) {
                       answer = n;
                       return answer;
                   }
               }
            }
            
        }
        
        return answer;
    }
}