[Programmers] Lv.1 | [PCCE 기출문제] 10번 / 공원 | Java

문제

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

 

지민이는 다양한 크기의 정사각형 모양 돗자리를 가지고 공원에 소풍을 나왔습니다. 공원에는 이미 돗자리를 깔고 여가를 즐기는 사람들이 많아 지민이가 깔 수 있는 가장 큰 돗자리가 어떤 건지 확인하려 합니다. 예를 들어 지민이가 가지고 있는 돗자리의 한 변 길이가 5, 3, 2 세 종류이고, 사람들이 다음과 같이 앉아 있다면 지민이가 깔 수 있는 가장 큰 돗자리는 3x3 크기입니다.

 

지민이가 가진 돗자리들의 한 변의 길이들이 담긴 정수 리스트 mats, 현재 공원의 자리 배치도를 의미하는 2차원 문자열 리스트 park가 주어질 때 지민이가 깔 수 있는 가장 큰 돗자리의 한 변 길이를 return 하도록 solution 함수를 완성해 주세요. 아무런 돗자리도 깔 수 없는 경우 -1을 return합니다.

---

제한사항

• 1 ≤ mats의 길이 ≤ 10
  • 1 ≤ mats의 원소 ≤ 20
  • mats는 중복된 원소를 가지지 않습니다.
• 1 ≤ park의 길이 ≤ 50
  • 1 ≤ park[i]의 길이 ≤ 50
  • park[i][j]의 원소는 문자열입니다.
  • park[i][j]에 돗자리를 깐 사람이 없다면 "-1", 사람이 있다면 알파벳 한 글자로 된 값을 갖습니다.

---

입출력 예

mats	park	result
[5,3,2]	[["A", "A", "-1", "B", "B", "B", "B", "-1"], ["A", "A", "-1", "B", "B", "B", "B", "-1"], ["-1", "-1", "-1", "-1", "-1", "-1", "-1", "-1"], ["D", "D", "-1", "-1", "-1", "-1", "E", "-1"], ["D", "D", "-1", "-1", "-1", "-1", "-1", "F"], ["D", "D", "-1", "-1", "-1", "-1", "E", "-1"]]	3

 

---

입출력 예 설명

입출력 예 #1

• 지문과 동일합니다.

---

 

• cpp를 응시하는 경우 리스트는 배열과 동일한 의미이니 풀이에 참고해주세요.ㅠ
  • ex) 번호가 담긴 정수 리스트 numbers가 주어집니다. => 번호가 담긴 정수 배열 numbers가 주어집니다.
• java를 응시하는 경우 리스트는 배열, 함수는 메소드와 동일한 의미이니 풀이에 참고해주세요.
  • ex) solution 함수가 올바르게 작동하도록 한 줄을 수정해 주세요. => solution 메소드가 올바르게 작동하도록 한 줄을 수정해 주세요.

---

풀이

import java.util.Arrays;

class Solution {
    public int solution(int[] mats, String[][] park) {
        // 1. 돗자리 크기를 작은 것부터 큰 순으로 정렬
        //    나중에 큰 돗자리부터 확인할 때 인덱스를 역순으로 돌기 위해
        Arrays.sort(mats);

        int rows = park.length;       // 공원의 세로 길이 (총 행 개수)
        int cols = park[0].length;    // 공원의 가로 길이 (총 열 개수)

        // 2. 큰 돗자리부터 하나씩 시도
        for (int mIdx = mats.length - 1; mIdx >= 0; mIdx--) {
            int size = mats[mIdx];  // 이번에 확인할 돗자리 한 변 길이

            // ------------------------------------------------------------
            // 반복문 범위 설정 (i, j)
            // - i : 돗자리의 왼쪽 위 시작 행
            // - j : 돗자리의 왼쪽 위 시작 열
            //
            // 세로 범위:
            //   돗자리 맨 아래 행 = i + (size - 1)
            //   공원 맨 아래 행 = rows - 1
            //   돗자리 끝이 공원을 벗어나지 않도록:
            //       i + (size - 1) <= rows - 1
            //   → i <= rows - size
            //
            // 가로 범위는 같은 원리:
            //       j <= cols - size
            // ------------------------------------------------------------

            for (int i = 0; i <= rows - size; i++) {
                for (int j = 0; j <= cols - size; j++) {

                    boolean canPlace = true;  // 이 위치에 돗자리를 깔 수 있다고 가정

                    // 3. (i, j)를 왼쪽 위로 하는 size x size 구역 확인
                    //    r < i + size 와 c < j + size의 의미:
                    //    - r = i부터 시작해서 size칸만큼 내려감 (총 size칸)
                    //    - c = j부터 시작해서 size칸만큼 오른쪽으로 이동 (총 size칸)
                    //    이렇게 하면 돗자리의 모든 칸을 검사 가능
                    for (int r = i; r < i + size; r++) {
                        for (int c = j; c < j + size; c++) {

                            // 사람이 있는 칸이면 이 위치에 돗자리를 깔 수 없음
                            if (!park[r][c].equals("-1")) {
                                canPlace = false;

                                // -------------------------
                                // break의 의미 (1)
                                // 현재 행(r)에서 오른쪽으로 더 볼 필요 없음
                                // 이미 사람이 있으므로, 이 행의 나머지 칸은 스킵
                                // -------------------------
                                break;  
                            }
                        }

                        // -------------------------
                        // break의 의미 (2)
                        // 이미 canPlace = false 이므로
                        // 돗자리 전체 구역을 검사할 필요 없음
                        // 다음 (i,j) 위치로 바로 넘어가야 함
                        // -------------------------
                        if (!canPlace) break;  
                    }

                    // 4. 만약 해당 위치에 깔 수 있으면, 바로 그 크기를 리턴
                    if (canPlace) {
                        return size;
                    }
                }
            }
        }

        // 5. 모든 돗자리를 확인했는데 깔 수 없으면 -1 반환
        return -1;
    }
}