[코테연습] [PCCE 기출문제] 10번 / 공원

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

문제 타입

• 구현 문제
  • 2차원 배열(공원)을 기반으로 특정 크기의 정사각형 영역을 탐색하고 배치 가능 여부를 판단하는 문제.
• 브루트 포스 탐색
  • 가능한 모든 시작 위치에서 주어진 크기의 매트를 배치할 수 있는지 확인하는 완전 탐색 문제.
• 최적화 문제
  • 가장 큰 매트를 배치하는 것이 목표로, 탐색 순서를 최적화할 수 있음.

---

문제 분석

• 입력
  • mats: 매트 크기의 정수 배열 (각 원소는 정사각형 매트의 한 변의 길이).
  • park: 공원의 상태를 나타내는 2차원 문자열 배열 (각 셀은 비었는지 여부를 나타냄).
    • "-1": 비어 있음.
    • 다른 값: 비어 있지 않음.
• 출력
  • 공원에 배치할 수 있는 가장 큰 매트 크기 (한 변의 길이). 배치가 불가능하면 -1 반환.
• 핵심 조건
  • 매트는 size x size 크기이며, 시작 위치부터 해당 크기의 모든 영역이 비어 있어야 배치 가능.
  • 여러 매트 크기 중 가장 큰 매트만 배치 가능.
• 제약 조건
  • 공원의 크기보다 매트 크기가 크면 배치 불가.
  • 모든 매트 크기를 공원에서 순차적으로 확인해야 함.

---

문제 풀이

1. 매트 크기 정렬
   • 매트 크기를 오름차순으로 정렬하여 큰 크기부터 확인.
   • 큰 매트가 배치되면 이후 매트는 확인할 필요가 없으므로 효율적.
2. 2차원 배열 탐색
   • 공원의 가능한 시작 위치 (i, j)를 모두 확인.
   • 시작 위치에서 size x size 영역이 모두 비어 있는지 확인.
3. 영역 확인
   • 시작 위치 (i, j)부터 size x size 영역의 모든 셀이 "-1"인지 검사.
   • 영역 내 하나라도 비어 있지 않다면 해당 위치에서는 배치 불가.
4. 결과 반환
   • 가장 큰 매트를 배치할 수 있으면 해당 크기를 반환.
   • 모든 매트가 배치 불가능하면 -1 반환.

 

import java.util.*;

class Solution {
    public int solution(int[] mats, String[][] park) {
        // 매트 크기를 오름차순으로 정렬
        Arrays.sort(mats);
        
        // 정렬된 매트 크기를 큰 순서대로 확인
        for (int i = mats.length - 1; i >= 0; i--) {
            // 현재 매트 크기를 공원에 배치할 수 있는지 확인
            if (canPlaceMat(park, mats[i])) {
                return mats[i]; // 배치할 수 있다면 해당 매트 크기를 반환
            }
        }
        
        return -1; // 배치할 수 있는 매트가 없다면 -1 반환
    }

    private static boolean canPlaceMat(String[][] park, int size) {
        int rows = park.length; // 공원의 행(row) 개수
        int cols = park[0].length; // 공원의 열(column) 개수

        // 공원에서 매트를 배치할 수 있는 모든 시작 위치를 확인
        for (int i = 0; i <= rows - size; i++) {
            for (int j = 0; j <= cols - size; j++) {
                // (i, j) 위치에서 주어진 크기의 매트를 배치할 수 있는지 확인
                if (isAreaEmpty(park, i, j, size)) {
                    return true; // 배치할 수 있다면 true 반환
                }
            }
        }
        return false; // 배치할 수 없다면 false 반환
    }

    private static boolean isAreaEmpty(String[][] park, int startX, int startY, int size) {
        // 지정된 시작 위치에서 size x size 크기의 영역이 비었는지 확인
        for (int i = startX; i < startX + size; i++) {
            for (int j = startY; j < startY + size; j++) {
                // 해당 영역에 "-1"이 아닌 값이 있으면 비어 있지 않음
                if (!park[i][j].equals("-1")) { 
                    return false; // 비어 있지 않으므로 false 반환
                }
            }
        }
        return true; // 영역이 모두 비어 있으면 true 반환
    }
}