[Programmers] PCCE 기출문제 10번 / 공원 Java

반응형

728x90

[Programmers] PCCE 기출문제 10번 / 공원 - LV 1

---

접근

• 그리디

---

풀이

PCCE 기출문제 10번 공원 문제로 사람들을 피해 가장 큰 돗자리를 펴는 문제이다. 2차원 배열을 탐색하며 가지고 있는 정사각형 돗자리 중 가장 큰 돗자리를 구해야 하는데 중첩문이 많이 나오는 문제이다. 이런 문제를 싫어하기도 하고 정말 생각한 대로 풀면 풀어지는 문제 이긴 하나 어쨌든 참 귀찮은 문제이다.

	int rows = park.length;
        int cols = park[0].length;
        int maxSize = -1;

        Arrays.sort(mats);

코드가 복잡하기 때문에 행과 열을 변수로 뽑아주고 돗자리의 크기를 저장할 변수를 선언했다. 돗자리의 크기는 정렬을 해주어 크기별로 접근할 수 있게 해 준다.

 	for (int m = mats.length - 1; m >= 0; m--) {
            boolean canPlace = false;

            for (int i = 0; i <= rows - mats[m]; i++) {
                for (int j = 0; j <= cols - mats[m]; j++) {
                    boolean allMinusOne = true;

벌써 반복문 중첩이 3번이나 되었다. 돗자리의 크기가 오름차순으로 정렬되어 있기 때문에 큰 순으로 접근하기 위해 마지막 인덱스부터 반복을 시작한다. 처음 문제를 풀 때 중첩이 많이 나올 거 같아 인덱스 접근이 필요 없어 보이는 것들은 개선된 for문으로 돌리기 위해 내림차순으로 정렬해 주었는데 직접 수동으로 내림차순 정렬을 해준 뒤 사용하거나 그냥 박싱을 통해 Integer 리스트로 바꿔서 정렬 해 버려도 넉넉하게 시간 안에 통과할 수 있어 편한 대로 사용하면 된다. 돗자리를 펼칠 수 있는지를 체크하는 flag로 사용할 변수를 선언하고 반복을 시작하는데 돗자리의 길이를 빼주어 불 필요한 반복을 제거해 주었다. 

		    for (int x = i; x < i + mats[m]; x++) {
                        for (int y = j; y < j + mats[m]; y++) {
                            if (!park[x][y].equals("-1")) {
                                allMinusOne = false;
                                break;
                            }
                        }
                        if (!allMinusOne) break;

반복문 2개 추가로 총 5중 중첩문이 탄생했다. 실질적인 돗자리 배치 구역을 검사하는 부분으로 현재 구역이 -1로 비어있는지 체크를 하고 비어있지 않다면 그 구역에는 돗자리 설치가 불가하여 검사를 중단한다.

		    if (allMinusOne) {
                        canPlace = true;
                        break;
                    }
                }
                if (canPlace) break;
            }

            if (canPlace) {
                maxSize = mats[m];
                break;  
            }
        }

        return maxSize;

변경된 상태 flag를 통해서 현재 구역에 돗자리 배치가 가능했는지를 알아보고 가능하다면 현재 돗자리가 최대 사이즈이므로 탐색을 종료하고 반환한다. 

---

전체 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] mats, String[][] park) {
        int rows = park.length;
        int cols = park[0].length;
        int maxSize = -1;

        Arrays.sort(mats);

        for (int m = mats.length - 1; m >= 0; m--) {
            boolean canPlace = false;

            for (int i = 0; i <= rows - mats[m]; i++) {
                for (int j = 0; j <= cols - mats[m]; j++) {
                    boolean allMinusOne = true;
                 
                    for (int x = i; x < i + mats[m]; x++) {
                        for (int y = j; y < j + mats[m]; y++) {
                            if (!park[x][y].equals("-1")) {
                                allMinusOne = false;
                                break;
                            }
                        }
                        if (!allMinusOne) break;
                    }

                    if (allMinusOne) {
                        canPlace = true;
                        break;
                    }
                }
                if (canPlace) break;
            }

            if (canPlace) {
                maxSize = mats[m];
                break;  
            }
        }

        return maxSize;
    }
}

중간에 검사하는 부분이나 메서드로 뽑을 만한 부분이 있는데 뽑았다면 좀 더 보기 편했을 거 같긴 하다.