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

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

• 지문과 동일합니다.

---

공원에 깔 수 있는 최대 돗자리의 길이를 구하는 문제입니다.

 

문제를 처음 보고 반복문을 마구 써서 풀어도 될지 고민을 많이 했는데, 그냥 5중 반복문을 사용하는 것으로 문제를 풀었습니다.

PCCE인 만큼 굳이 그렇게까지 어려운 풀이를 원하지 않을 것 같았거든요.

 

정답 코드를 작성해보겠습니다.

def solution(mats, park):
    # 공원의 가로 세로
    m, n = len(park), len(park[0]) 
    # 돗자리 크기를 정렬합니다.
    mats.sort(reverse=True)
    # 모든 정사각형 돗자리에 대해서 비교합니다.
    for mat in mats:
        # 가로 설정
        for i in range(m - mat + 1):
            # 세로 설정
            for j in range(n - mat + 1):
                # 비어있는 자리의 개수를 셉니다.
                count = 0
                # 모든 범위에 대해 탐색을 시작합니다.
                for k in range(mat):
                    for l in range(mat):
                        # 비어있는 자리일 때마다 1씩 더해줍니다.
                        if park[i + k][j + l] == "-1":
                            count += 1
                # 모든 범위가 비어있다면
                if count == mat ** 2:
                    # 해당 돗자리 길이를 반환합니다.
                    return mat
    # 이전에 반환되지 않았다면 -1을 반환합니다.
    return -1

 

저는 mats에서 돗자리의 길이를 하나씩 가져온다음, 공원의 모든 위치에 대해서 비교하는 식으로 문제를 풀었습니다.

시작 위치(i, j)로부터 mat의 길이만큼씩 비교를 하는 방법입니다. 그래서 빈 자리를 세준 다음, 해당 자리가 전부 비어있다면 mat의 제곱과 값이 같아지는 것을 사용했습니다.

만약 반환이 한 번도 되지 않았다면 어떤 돗자리도 깔 수 없기 때문에, -1을 반환해주도록 구현했습니다.

 

생각보다 고민하는데 시간을 많이 사용했습니다. 5중 반복문까진 좀 생각하기 어려웠네요.