[PCCE 기출문제] 10번 / 공원 - JAVA

문제 설명

 

제한사항

 

입출력 예

 

문제 설명:
1.처음 문제에 접근했을 때는 그래프 탐색 문제라 생각했습니다.
2.문제를 보니 단순 구현 + 완전 탐색 문제였습니다.
3.-1이 빈칸이며 기존의 깔린 돗자리를 제외하고 현재 남은 구역 중에 제일 큰 돗자리를 펼 수 있는 공간을 찾는 문제였습니다.
4.완전 탐색으로 돗자리를 다 활용하고 그중에서 제일 큰 돗자리를 저장하고 출력하는 방식으로 접근했습니다.
5.필 수 있는 돗자리가 없다면 -1을 출력해줍니다.

 

전체 코드

import java.util.*;
class Solution {
    public int solution(int[] mats, String[][] park) {
        int answer = -1;
        //어떤 돗자리가 젤 큰지 저장하기 위함 list
        List<Integer> list = new ArrayList<>();
        //공원 크기 
        int n = park.length;
        int m = park[0].length;
        for(int i = 0 ; i<n ; i++){
            for(int j = 0; j<m; j++){
                //돗자리를 필 수 있다면 로직 시작
                if(park[i][j].equals("-1")){
                    // mats에 있는 모든 돗자리를 탐색
                    //5,3,2 이면 5*5, 3*3 ,2*2가 가능한 지 탐색
                    for(int k = 0; k<mats.length; k++){
                        int num = mats[k];
                        int count = 0 ;
                        for(int x = i; x<i+num; x++){
                            for(int y = j; y<j+num; y++){
                                if(x < 0 || x >= n || y < 0|| y >= m){
                                    continue;
                                }
                                if(park[x][y].equals("-1")){
                                    count++;
                                }
                            }
                        }
                        
                        if(count == num*num){
                            list.add(num);
                        }
                    }
                }
            }
        }
        
        //가능한 돗자리가 없다면 -1
        if(list.size() == 0){
            answer = -1;
        }else{
            //가능한 돗자리가 있다면 그중에 젤 큰 사이즈 저장
            Collections.sort(list);
            answer = list.get(list.size()-1);
        }
        return answer;
    }
}