[프로그래머스] (Java) [PCCE 기출문제] 10번 / 공원 문제풀이

 

 

📑 1. 문제설명

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

문제 요약

• park : 공원 자리 배치. "-1"이면 빈 자리, 다른 값이면 사람이 앉아 있음
• mats : 지민이가 가진 돗자리 크기가 담긴 배열이다. 각 요소는 한 변의 길이
• 목표 : 공원에서 사람이 없는 영역("-1")을 찾아서, 지민이가 가진 돗자리 중 가장 큰 크기를 깔 수 있는지 확인하는 코드짜기

---

💡 2. 풀이과정

생각해 볼 문제

1. 가장 큰 돗자리 구하기

• 문제에서 가장 큰 돗자리를 구하라고 했으니까 큰 돗자리부터 깔아보고, 가능하면 바로 결과 리턴할 수 있도록 한다.
• 이 부분은 돗자리의 길이가 담긴 배열 mats를 오름차순 정렬 후 역순 탐색으로 처리했다.

---

2. 공원 탐색할 때 공원에서 돗자리 놓을 수 있는 시작점 범위 

• park를 2차원 배열이라고 생각하고, 각 좌표 (i, j)를 시작점으로 돗자리를 깔 수 있는지 확인한다.
• 이 때 돗자리 한 변 길이를 k라고 하면, 아래 조건을 만족해야 돗자리가 범위 안에 있는 것이다. 

 쉽게 말하면, 여기서 시작점 탐색은 공원 배열 park에서 돗자리 왼쪽 위 모서리 위치를 정하는 과정이다. 돗자리를 어디에 놓을지 기준점을 (i, j)로 잡는 것이다. 이 과정이 중요한 이유는 돗자리 한 변 길이를 k라고 하면, (i, j)가 시작점일 때 돗자리가 공원을 벗어나면 안 되기 때문에 아래와 같이 범위를 설정해 준다. 

i + k <= park.length
j + k <= park[0].length

• 예: 세로 6, 가로 8, 돗자리 3x3이면
  • i: 0~3 (0,1,2,3)
  • j: 0~5 (0,1,2,3,4,5)

for (int i = 0; i <= rows - k; i++) {
    for (int j = 0; j <= cols - k; j++) {
        // (i,j)를 왼쪽 위 모서리로 돗자리 놓기
    }
}

 

---

 

3. 빈 공간 확인하는 로직

• 시작점 (i, j)에서 k * k 범위 내 모든 칸이 "-1"인지 확인하기
  • 하나라도 사람이 있으면 해당 위치는 불가능
  • 모든 칸이 "-1"이면 해당 돗자리 사용 가능

---

4. 결과 처리

• 가장 큰 돗자리부터 확인했으므로, 가능하면 바로 그 크기를 리턴하면 된다.
• 모든 돗자리 사용 불가 시 -1을 리턴한다. 

---

👨‍💻 3. 정답코드

import java.util.*;

class Solution {
    public int solution(int[] mats, String[][] park) {
        // 1. 큰 돗자리부터 확인하기
        Arrays.sort(mats);
        int n = mats.length;
        
        int rows = park.length;
        int cols = park[0].length;
        
        for (int idx = n - 1; idx >= 0; idx--) { // 큰 것부터 확인
            int k = mats[idx];
            
            // 2. 시작점
            for (int i = 0; i <= rows - k; i ++) {
                for (int j = 0; j <= cols - k; j++) {
                    boolean canPlace = true;
                    
                    // 3. k * k 확인하기
                    for (int x = i; x < i + k; x++) {
                        for (int y = j; y < j + k; y++) {
                            if (!park[x][y].equals("-1")) {
                                canPlace = false;
                                break;
                            }
                        }
                        if (!canPlace) break; // false 나오면 다음 반복으로
                    }
                    
                    // 4. 돗자리 놓을 수 있으면 return
                    if (canPlace) {
                        return k;
                    }
                }
            }            
        }
    
        return -1;    
    }
}

코드 포인트

1. Arrays.sort(mats) → 오름차순 정렬 후 큰 것부터 확인
2. (i, j)를 시작점으로 k * k 영역 체크
3. 하나라도 사람이 있으면 canPlace = false
4. 가장 큰 돗자리부터 체크하므로, 가능하면 바로 return
5. 놓을 수 없으면 -1 리턴