공원_복습

2026.07.10

문제 풀이

1차 실행 오류

---

30/100

실패

---

코드 분석

내림차순으로 정렬된 각 매트가 공원에 배치될 수 있는지를 비교

for문 5개를 이용했다.

첫번째 for문은 매트의 크기
두번째, 세번째 for문은 가능한 시작점의 위치
세번째, 네번째 for문은 해당 범위 내 배치 가능 여부

---

class Solution {
    public int solution(int[] mats, String[][] park) {
        int height = park.length; // 공원 전체 높이
        int width = park[0].length; // 공원 전체 너비
        
        boolean available = true;
        
        for (int mat : mats) {
            for (int i = 0; i <= height - mat; i++) {
                for (int j = 0; j <= width - mat; j++) {
                    available = true;
                    for (int p = i; p < i + mat; p++) {
                        if (!available) {
                            break;
                        }
                        for (int q = j; q < j + mat; q++) {
                            if (!park[p][q].equals("-1")) {
                                available = false;
                                break;
                            }
                        }
                    }
                    if (available) {
                        return mat;
                    }
                }   
            }   
        }
        return -1;
    }
}

나의 코드

---

실패 원인

mats 배열이 내림차순으로 정렬되어 있지 않는 것이 원인이었음

---

소요 시간

1시간

---

시간 복잡도

H = height, W = width, K = mats.length, m = 각 매트 크기

O(K × H × W × m_max²)

---

import java.util.Arrays;

class Solution {
    public int solution(int[] mats, String[][] park) {
        int height = park.length; // 공원 전체 높이
        int width = park[0].length; // 공원 전체 너비
        
        boolean available = true;
        
        // mats 내림차순으로 정렬
        Arrays.sort(mats);
        int len = mats.length;
        int[] mat = new int[len];
        for (int i = 0; i < len; i++) {
            mat[len - i - 1] = mats[i];
        }
        
        for (int m : mat) {
            for (int i = 0; i <= height - m; i++) {
                for (int j = 0; j <= width - m; j++) {
                    available = true;
                    for (int p = i; p < i + m; p++) {
                        if (!available) {
                            break;
                        }
                        for (int q = j; q < j + m; q++) {
                            if (!park[p][q].equals("-1")) {
                                available = false;
                                break;
                            }
                        }
                    }
                    if (available) {
                        return m;
                    }
                }   
            }   
        }
        return -1;
    }
}

AI 코드

---

코드 분석

obstacle[]로 가능한 구역은 0, 불가능한 구역은 1로 설정
prefix[]를 통해 사각형 범위 내 배치 불가능한 지역 개수 표시

obstacle[] 
[1, 1, 0, 1, 1, 1, 1, 0]
[1, 1, 0, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 0, 0, 1]
[1, 1, 0, 0, 0, 0, 1, 0]

prefix[]
[ 0,  0,  0,  0,  0,  0,  0,  0,  0]
[ 0,  1,  2,  2,  3,  4,  5,  6,  6]
[ 0,  2,  4,  4,  6,  8, 10, 12, 12]
[ 0,  2,  4,  4,  6,  8, 10, 12, 12]
[ 0,  3,  6,  6,  8, 10, 12, 15, 15]
[ 0,  4,  8,  8, 10, 12, 14, 17, 18]
[ 0,  5, 10, 10, 12, 14, 16, 20, 21]

prefix[i + 1][j + 1] = obstacle[i][j] 
+ prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];

prefix[i + 1][j + 1]은 obstacle[i][j]의 위치와 대응함
따라서 obstacle[i][j]는 prefix[i + 1][j + 1] 현재 위치의 장애물을 의미

prefix[i][j + 1] + prefix[i + 1][j]는 이전 장애물의 개수를 의미

prefix[i][j]는 이전 장애물에서 겹치는 부분을 의미

---

int sum = prefix[i + m][j + m] - prefix[i][j + m]
                            - prefix[i + m][j] + prefix[i][j];
                            
해당 코드에서도 같은 방시으로 prefix를 이용해 해당 범위 내의 장애물이 있는지 점검

---

시간 복잡도

$O(K × H × W)$

---

import java.util.Arrays;

class Solution {
    public int solution(int[] mats, String[][] park) {
        int height = park.length;
        int width = park[0].length;

        // 1) 장애물 여부를 0/1로 표시 (park[i][j]가 "-1"이면 0, 아니면 1)
        int[][] obstacle = new int[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                obstacle[i][j] = park[i][j].equals("-1") ? 0 : 1;
            }
        }

        // 2) 2차원 누적합 배열 만들기 (1-indexed로 여유 한 칸 추가)
        int[][] prefix = new int[height + 1][width + 1];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                prefix[i + 1][j + 1] = obstacle[i][j]
                        + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
            }
        }

        // 3) mats 내림차순 정렬
        Integer[] mat = Arrays.stream(mats).boxed().toArray(Integer[]::new);
        Arrays.sort(mat, (a, b) -> b - a);

        // 4) 큰 매트부터 시도, 배치 가능하면 바로 반환
        for (int m : mat) {
            for (int i = 0; i + m <= height; i++) {
                for (int j = 0; j + m <= width; j++) {
                    int sum = prefix[i + m][j + m] - prefix[i][j + m]
                            - prefix[i + m][j] + prefix[i][j];
                    if (sum == 0) { // 장애물이 하나도 없음
                        return m;
                    }
                }
            }
        }
        return -1;
    }
}