프로그래머스 | Python | BruteForce, Greedy | 공원 (Lv.1)

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

프로그래머스

 

def solution(mats, park):
    H, W = len(park), len(park[0])  # 공원의 크기
    mats.sort(reverse=True)  # 가장 큰 돗자리부터 탐색

    # 특정 위치에서 k x k 크기의 돗자리를 놓을 수 있는지 확인하는 함수
    def can_place(r, c, k):
        if r + k > H or c + k > W:  # 돗자리가 공원을 벗어나면 불가능
            return False
        return all(park[i][j] == "-1" for i in range(r, r + k) for j in range(c, c + k)) 

    # 가장 큰 돗자리부터 배치 시도
    for size in mats:
        for i in range(H - size + 1):  # 굳이 공원 끝까지 돌 필요 없음
            for j in range(W - size + 1):
                if can_place(i, j, size):
                    return size  # 가장 큰 돗자리 찾으면 즉시 반환

    return -1  # 모든 돗자리를 놓을 수 없는 경우

---

답변 작성까지의 생각의 흐름

1. 문제를 분석한다

문제를 읽고 핵심 요구 사항을 정리한다.

✅ 목표:

• 공원에서 돗자리를 깔 수 있는 가장 큰 크기를 찾아야 한다.
• 돗자리는 완전히 빈 공간("-1")에만 배치 가능해야 한다.
• 가장 큰 돗자리부터 배치를 시도하고, 배치할 수 있다면 그 크기를 반환한다.
• 어떤 돗자리도 놓을 수 없다면 -1을 반환한다.

✅ 입력 조건:

• mats: 가능한 돗자리의 크기 리스트 (중복 없음)
• park: 공원의 자리 배치도 (2차원 리스트)

---

2. 문제 해결을 위한 전략을 세운다

접근 방법

1️⃣ 큰 돗자리부터 배치를 시도한다.

• 큰 돗자리를 배치할 수 있으면 작은 돗자리는 고려할 필요 없음.
• 돗자리를 내림차순 정렬(sort(reverse=True)).

2️⃣ 공원의 가능한 모든 위치에서 돗자리 배치 가능 여부를 확인한다.

• 돗자리의 왼쪽 상단 기준으로 k × k 크기가 비어 있는지 확인.
• can_place(r, c, k) 함수를 만들어서 배치 가능 여부를 판단한다.

3️⃣ 공원 끝까지 검사할 필요 없이 최적화

• i와 j를 H - size + 1, W - size + 1까지만 순회
• 공원을 벗어나는 탐색을 미리 방지하여 연산을 줄인다.

4️⃣ 배치 가능한 가장 큰 돗자리를 찾으면 즉시 반환

• 불필요한 연산을 최소화하여 빠른 결과 반환

---

코드 동작 흐름

def solution(mats, park):

1. 공원의 크기 저장

    H, W = len(park), len(park[0])  # 공원의 크기

• H: 공원의 세로 길이(행 개수)
• W: 공원의 가로 길이(열 개수)

---

2. 돗자리를 큰 순서대로 정렬

    mats.sort(reverse=True)  # 가장 큰 돗자리부터 탐

• 큰 돗자리부터 배치 시도
• 이유: 큰 돗자리를 배치할 수 있으면 그게 정답이므로 작은 돗자리는 고려할 필요가 없음

---

3. 특정 위치에서 돗자리를 놓을 수 있는지 검사하는 함수

    def can_place(r, c, k):
        if r + k > H or c + k > W:  # 돗자리가 공원을 벗어나면 불가능
            return False
        return all(park[i][j] == "-1" for i in range(r, r + k) for j in range(c, c + k))

✅ 이 함수의 역할

1. r, c를 좌측 상단으로 k × k 크기의 돗자리를 놓을 수 있는지 확인
2. 만약 공원 범위를 벗어나거나(r + k > H 또는 c + k > W)
   • 배치할 수 없으므로 False 반환
3. 배치하려는 영역 안에 사람이 없는지 확인
   • all(park[i][j] == "-1" for i in range(r, r + k) for j in range(c, c + k))
   • range(r, r + k)를 사용하면 r부터 r + k - 1까지만 포함하므로 정확히 k x k 크기만큼 탐색.
   • 공원의 k × k 영역이 전부 "-1"이면 배치 가능

1️⃣ 가장 먼저 해야 할 일 → "어떤 돗자리를 먼저 확인할 것인가?"

• 여러 개의 돗자리를 가지고 있음.
• 큰 돗자리부터 확인해야 작은 돗자리를 고려할 필요가 줄어듦.
• 따라서 mats.sort(reverse=True)를 사용하여 큰 크기부터 차례대로 탐색.

---

2️⃣ 다음으로 해야 할 일 → "돗자리를 어디에 놓을 것인가?"

• 돗자리는 공원의 빈 공간("-1")에만 놓을 수 있음.
• 공원의 모든 위치를 확인하며, 돗자리를 놓을 수 있는지 검사해야 함.
• for i in range(H), for j in range(W)를 이용해 공원의 모든 칸에서 배치 가능 여부 확인.

---

3️⃣ 문제 발생 → "매번 k x k 범위를 어떻게 확인할 것인가?"

• 돗자리를 배치하려면 (i, j)를 왼쪽 상단 기준으로 k x k 크기가 비어 있는지 확인해야 함.
• 반복해서 같은 조건을 확인해야 하므로, 이를 함수로 분리하면 코드 가독성이 좋아짐.

---

4️⃣ can_place(r, c, k) 함수를 만들 필요성이 자연스럽게 떠오름

• (r, c) 위치에서 k x k 크기의 공간이 비어 있는지 확인하는 로직이 필요함.
• 공원 밖으로 벗어나지 않는지도 체크해야 함.
• 이러한 반복적인 검사를 함수로 분리하면 코드가 더 직관적이 됨.

---

💡 can_place()를 함수로 만든 이유

• i, j를 기준으로 k x k 크기의 영역을 검사하는 반복적인 코드가 필요했기 때문.
• 공원 밖으로 벗어나는지 (범위 체크)
• 사람이 있는지 (빈 공간 체크)
• 이 두 가지 조건을 매번 for문 안에서 검사하면 코드가 길어지고 복잡해짐.
• 함수를 만들면 가독성이 좋아지고 유지보수도 편해짐.

---

4. 가장 큰 돗자리부터 배치 시도

    for size in mats:  # 가장 큰 돗자리부터 배치 시도

• 큰 돗자리부터 순서대로 탐색
• 작은 돗자리는 큰 돗자리가 배치되지 않았을 때만 고려

---

5. 공원 내에서 배치 가능한 위치 탐색

        for i in range(H - size + 1):  # 굳이 공원 끝까지 돌 필요 없음
            for j in range(W - size + 1):

• 불필요한 탐색을 줄이기 위해 최적화
• i와 j가 H - size + 1과 W - size + 1까지만 순회하는 이유는?
  • 돗자리가 배치될 공간이 부족한 부분은 탐색할 필요가 없기 때문!
  • 예를 들어 H = 6이고 size = 3이면, i = 4 이상에서는 돗자리 배치 불가

---

6. 돗자리 배치 가능 여부 확인

                if can_place(i, j, size):
                    return size  # 가장 큰 돗자리 찾으면 즉시 반환

• can_place(i, j, size)를 호출하여 해당 위치에 배치 가능 여부 확인
• 배치 가능하면 바로 돗자리 크기 반환 → 더 작은 크기는 고려할 필요 없음

---

7. 모든 돗자리를 놓을 수 없는 경우

    return -1  # 모든 돗자리를 놓을 수 없는 경우

• 탐색이 끝났는데도 돗자리를 놓을 곳이 없으면 -1 반환

---

3. 예제 실행 흐름

예제 1

mats = [5,3,2]
park = [
    ["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"]
]

실행 과정

1. mats 정렬 → [5, 3, 2]
2. size = 5부터 배치 시도 → 불가능
3. size = 3 배치 시도 → 가능한 위치 발견!
4. return 3 (최대 크기의 돗자리)

✅ 출력: 3

---

4. 핵심 정리

 

단계	동작
1	공원의 크기(H, W)를 구함
2	돗자리 크기 목록(mats)을 내림차순 정렬
3	돗자리를 놓을 수 있는지 확인하는 함수(can_place) 정의
4	가장 큰 돗자리부터 공원의 가능한 위치에서 배치 시도
5	배치 가능하면 즉시 해당 크기 반환
6	모든 돗자리를 놓을 수 없다면 -1 반환

---

5. 시간 복잡도 분석

• 돗자리 개수: 최대 10
• 공원 크기: 최대 50 × 50 = 2500
• 최대 연산량:
  • 10 × 2500 = 25,000 (최악의 경우) → 충분히 빠르게 실행 가능!

✅ 효율적인 탐색을 위한 최적화가 적용된 코드!

✅ 큰 돗자리부터 탐색하여 불필요한 계산을 최소화!