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

코드 힌트:

1. 문제 이해:
   • mats 배열은 정사각형의 돗자리로 현재 공원에 놓을 수 있는 가장 큰 돗자리의 크기를 구하는데 사용하는 배열입니다.
   • park는 n x m 크기의 공원 맵으로, 매트가 놓일 수 있는 빈 공간은 "-1"로 표시되어 있습니다. 매트는 "-1"로 표시된 빈 공간에만 놓일 수 있습니다.
   • 목표는 "-1"로 표시된 빈 공간 중 가장 큰 매트가 들어갈 수 있는 위치를 찾는 것입니다.
2. 매트 놓기:
   • 각 빈 공간("-1")에서 매트가 들어갈 수 있는 가장 큰 크기를 찾는 것이 목표입니다.
   • 공원 맵을 순회하면서 빈 공간이 나오면 그 위치를 기준으로 mats 배열에 있는 매트 크기 중 들어갈 수 있는 최대 크기를 찾습니다.
   • 매트는 정사각형이므로 해당 위치에서 매트가 들어갈 수 있는지를 확인해야 합니다.
3. 매트 크기 확인:
   
   • 주어진 매트 크기가 해당 위치에서 공원 맵 경계를 넘지 않는지 확인하고, 그 안에 "-1"만 있는지 체크합니다.
   • 해당 매트가 들어갈 수 있는지 여부를 파악을 해야합니다. 만약 매트 크기만큼의 영역이 모두 "-1"이면 그 매트는 들어갈 수 있습니다.
   • 해당 여부는 2중 for문을 사용하였고 flag 변수를 선언하여 true, false로 확인했습니다.
4. 효율성 고려:
   • 매트 크기가 클수록 먼저 확인하여 가장 큰 매트를 먼저 놓을 수 있는지를 따집니다. 그러므로 mats 배열을 내림차순으로 순회합니다.
   • 만약 가장 큰 매트 크기와 일치하는 매트가 놓였으면 바로 결과를 반환합니다.
5. 예외 처리:
   • 만약 매트가 놓일 수 없는 경우에는 결과 값이 -1로 유지됩니다.
   • park 맵이 경계를 넘지 않도록 체크하며, 그 안에 "-1" 외의 값이 있을 경우 해당 매트는 놓일 수 없다는 의미입니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int[] mats, String[][] park) {
        // 결과값을 저장할 변수를 초기화
        int result = -1;
        
        // 매트를 크기순으로 정렬
        Arrays.sort(mats);
        int n = park.length; // 공원의 행 크기
        int m = park[0].length; // 공원의 열 크기
        
        // 공원의 모든 좌표를 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 공원 좌표가 '-1'일 때, 해당 좌표에서 시작할 수 있는 가장 큰 매트 크기를 찾는다
                if (park[i][j].equals("-1")) {
                    result = Math.max(getMaxSize(mats, park, i, j), result);
                    
                    // 만약 가장 큰 매트가 놓여질 수 있다면 탐색을 종료하고 결과를 반환
                    if (result == mats[mats.length-1])
                        return result;
                }
            }
        }
        
        return result;
    }
    
    public int getMaxSize(int[] mats, String[][] park, int x, int y) {
        // 현재 위치에서 가장 큰 매트 크기를 저장할 변수
        int maxSize = -1;
        int n = park.length; // 공원의 행 크기
        int m = park[0].length; // 공원의 열 크기
        
        // 가장 큰 매트 크기부터 작은 매트 크기까지 순차적으로 검사
        for (int i = mats.length - 1; i >= 0; i--) {
            int size = mats[i]; // 현재 검사 중인 매트의 크기
            
            // 매트가 공원 범위를 벗어나면 검사하지 않는다
            if (x + size - 1 >= n || y + size - 1 >= m)
                continue;
            
            boolean flag = true; // 매트를 놓을 수 있는지 여부를 저장할 플래그
            
            // 매트를 놓을 범위의 공원 좌표를 검사
            for (int j = x; j < x + size; j++) {
                for (int k = y; k < y + size; k++) {
                    // 공원의 해당 좌표가 '-1'이 아닌 경우, 매트를 놓을 수 없다
                    if (!park[j][k].equals("-1")) {
                        flag = false;
                        break;
                    }
                }
            }
            
            // 매트를 놓을 수 있는 경우, 해당 매트의 크기를 저장하고 종료
            if (flag) {
                maxSize = size;
                break;
            }
        }
        
        return maxSize; // 놓을 수 있는 가장 큰 매트 크기를 반환
    }
}