[프로그래머스/JAVA] 공원

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 💡 아이디어
• 👩🏻‍💻 최종 코드
• 🕑 시간 복잡도

 

 

 

🔗 문제 바로가기

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

프로그래머스

 

---

📌 문제 요약

 

 

주어진 공원 상태를 보고,

지민이가 가진 정사각형 돗자리들 중에서 깔 수 있는 가장 큰 돗자리의 크기를 찾아야 한다.

이때, 만약 깔 수 있는 돗자리가 없다면 -1을 반환해야 한다.

 

📥 입력

• mats
  • 지민이가 가진 돗자리들의 한 변 길이를 담은 정수 배열
  • ex. [5, 3, 2]가 주어진 경우, 지민이는 5*5, 3*3, 2*2 크기의 돗자리들을 가지고 있다.
• park
  • 공원의 상태를 나타낸 2차원 문자열 배열
  • "A", "B", "C" 같은 알파벳 → 이미 다른 사람이 앉아있는 곳
  • "-1" → 아무도 없는 빈자리

 

---

💡 아이디어

1️⃣ 돗자리 크기 정렬하기

문제에서 물어본 건 깔 수 있는 가장 큰 돗자리이기 때문에 크기 순으로 정렬하면 편할 것 같았다.

따라서 아래의 코드로 지민이가 가지 여러 개의 돗자리 크기를 오름차순으로 정렬해주었다.

Arrays.sort(mats);

 

 

2️⃣ 공원 크기 계산하기

park는 2차원 배열이고, [행][열] 구조이기 때문에

공원의 가로와 세로 크기를 아래의 코드로 구해주었다.

int width = park[0].length;
int height = park.length;

 

 

3️⃣ 가장 큰 돗자리부터 하나씩 확인하기

정렬된 mats 배열을 이용해서 가장 큰 크기부터 순서대로 꺼내 확인해주면 된다.

 

예를 들어 만약 우리가 정렬한 배열이 [2, 3, 5]였다면,

실제 검사할 때는 가장 큰 5부터 5, 3, 2 순서로 검사해주면 되는 것이다.

for (int k = mats.length - 1; k >= 0; k--) {
    int size = mats[k];
    ...
}

 

 

4️⃣ 공원의 모든 좌표에 대해 시도해보기

3번을 통해 현재 테스트 중인 돗자리의 크기 (size)를

이제 공원에 깔 수 있는지 모든 위치에서 시도해보면 된다.

 

이때, 공원 끝을 넘지 않도록 반복의 종료 조건을

i <= height - size, j <= width - size로 설정해주었다.

 

예를 들어 공원의 크기가 6 * 8인데, 돗자리의 크기가 3이면

어차피 i = 0 ~ 3, j = 0 ~ 5 이외의 위치는 돗자리를 까는 시작 범위가 될 수 없기 때문이다.

 

 

설치 시작 가능한 부분 = ✅

설치 시작 불가능한 부분 = 🚫

✅	✅	✅	✅	🚫	🚫
✅	✅	✅	✅	🚫	🚫
✅	✅	✅	✅	🚫	🚫
✅	✅	✅	✅	🚫	🚫
✅	✅	✅	✅	🚫	🚫
✅	✅	✅	✅	🚫	🚫
🚫	🚫	🚫	🚫	🚫	🚫
🚫	🚫	🚫	🚫	🚫	🚫

 

for (int i = 0; i <= height - size; i++) {
    for (int j = 0; j <= width - size; j++) {
        ...
    }
}

 

 

5️⃣ 해당 시작 위치에서 실제로 돗자리를 깔 수 있는지 검사하기

나는 아래와 같이 따로 calculate 함수를 만들어 분리해주었다.

private boolean calculate(String[][] park, int x, int y, int size){
        
    for(int i = x; i < x + size; i++){
        for(int j = y; j < y + size; j++){
            if(!park[i][j].equals("-1")){
                return false;
            }
        }
    }
        
    return true;
}

 

• x, y는 돗자리 깔기의 시작 위치
• size는 돗자리의 크기

 

• size 만큼 아래와 오른쪽으로 이동해보면서 돗자리 크기 만큼의 영역을 확인해본다.
• 이때, 중간에 하나라도 사람이 앉아있는 부분이 있다면, 돗자리를 깔 수 없으므로 바로 false를 반환해준다.
• 만약 반복문을 다 검사해서 통과했다면 돗자리를 깔 수 있으니 true를 반환한다.

 

---

👩🏻‍💻 최종 코드

import java.util.*;

class Solution {
    
    private boolean calculate(String[][] park, int x, int y, int size){
        
        for(int i = x; i < x + size; i++){
            for(int j = y; j < y + size; j++){
                if(!park[i][j].equals("-1")){
                    return false;
                }
            }
        }
        
        return true;
    }
    
    public int solution(int[] mats, String[][] park) {
        int width = park[0].length;
        int height = park.length;
        
        Arrays.sort(mats);
       
        for(int k = mats.length - 1; k >= 0; k--){
            int size = mats[k];
            
            for(int i = 0; i <= height - size; i++){
                for(int j = 0; j <= width - size; j++){
                    if(calculate(park, i, j, size)){
                        return size;
                    }
                }
            }
        }
        
        return -1;
    }
}

 

 

---

🕑 시간 복잡도

for (int k = mats.length - 1; k >= 0; k--) {         // (1) 돗자리 개수 만큼 반복
    int size = mats[k];
    
    for (int i = 0; i <= height - size; i++) {       // (2) 공원의 세로 크기 만큼 반복
        for (int j = 0; j <= width - size; j++) {    // (3) 공원의 가로 크기 만큼 반복
        
            if (calculate(park, i, j, size)) {       // (4) 해당 위치에 돗자리 깔 수 있는지 검사
                return size;
            }
        }
    }
}

 

for (int i = x; i < x + size; i++) {                 // size번 반복
    for (int j = y; j < y + size; j++) {             // size번 반복
        if (!park[i][j].equals("-1")) {
            return false;
        }
    }
}

 

 

• mats.length는 최대 10이므로 (1) 에서는 최대 반복 10회
• (i, j) 반복 부분에서는,
  • i는 최대 height - size + 1번 반복
  • j는 최대 width - size + 1번 반복 → 최대 50
  • 총 50 * 50 = 2500번 반복
• calculate에서는 한 번 호출 당 size * size 번 반복
  • 돗자리의 최대 크기는 20 * 20이니 최대 400번 반복

 

👉🏻 따라서 최종 시간 복잡도는 O(m × h × w × s² )이다.

(이 때, m은 돗자리 종류의 수, h와 w은 공원의 세로 가로 길이, s는 돗자리의 크기이다.)

 

n을 대략 50 정도로 보고 좀 더 단순화 한다면 O(n ^4)정도 될 것이다.