[PCCE 기출문제] 10번 / 공원
문제 설명
지민이는 다양한 크기의 정사각형 모양 돗자리를 가지고 공원에 소풍을 나왔습니다. 공원에는 이미 돗자리를 깔고 여가를 즐기는 사람들이 많아 지민이가 깔 수 있는 가장 큰 돗자리가 어떤 건지 확인하려 합니다. 예를 들어 지민이가 가지고 있는 돗자리의 한 변 길이가 5, 3, 2 세 종류이고, 사람들이 다음과 같이 앉아 있다면 지민이가 깔 수 있는 가장 큰 돗자리는 3x3 크기입니다.
지민이가 가진 돗자리들의 한 변의 길이들이 담긴 정수 리스트 mats, 현재 공원의 자리 배치도를 의미하는 2차원 문자열 리스트 park가 주어질 때 지민이가 깔 수 있는 가장 큰 돗자리의 한 변 길이를 return 하도록 solution 함수를 완성해 주세요. 아무런 돗자리도 깔 수 없는 경우 -1을 return합니다.
시각화
아래와 같이 맵이 주어지고 다른 사람들이 돗자리를 피고 앉아있다고 하자.
흰색 영역이 돗자리를 깔 수 있는 영역이다. 그중에서 가장 큰 정사각형을 보라색으로 표시하면 아래와 같다.
돗자리가 3개가 주어졌는데 2, 3, 5 이다.
보라색 영역에 돗자리를 깔 수 있는 가장 큰 정사각형은 3 X 3 이다. 5는 최대 크기인 4를 넘었기 때문에 가능하지 않다.
문제 해결 과정
Lv2. 가장 큰 정사각형 찾기 문제와 거의 유사하다. 그런데 이번 문제는 Lv1 인 이유는 아마 이중 for 문을 사용해도 통과하지 않을까 싶다. 그렇지만 빠른 방법으로 푸는 것이 더 좋기 때문에 dp 를 사용해서 풀어보자. 최대 정사각형 구하는 방법은 Lv2. 가장 큰 정사각형 찾기 을 참고하면 된다.
돗자리를 필 수 있는 영역 크기를 모두 저장하고 mats 에서 가장 큰 값을 찾아서 반환하면 된다. 간단한 문제이다.
전체 코드
한 줄 씩 내려가며 최대 값들을 설정해주면 된다.
def solution(mats, park):
square_maps = [[0] * len(park[0]) for _ in range(len(park))]
square_sizes = set()
for y in range(len(park)):
for x in range(len(park[y])):
if park[y][x] == "-1":
square_maps[y][x] = min(square_maps[y - 1][x - 1], square_maps[y - 1][x], square_maps[y][x - 1]) + 1
square_sizes.add(square_maps[y][x])
mats.sort(reverse=True)
for mat in mats:
if mat in square_sizes:
return mat
return -1
print(solution([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)
