[프로그래머스] [Python] [PCCE 기출문제] 10번 / 공원

1. 문제 설명

지민이는 다양한 크기의 정사각형 모양 돗자리를 가지고 공원에 소풍을 나왔습니다. 공원에는 이미 돗자리를 깔고 여가를 즐기는 사람들이 많아 지민이가 깔 수 있는 가장 큰 돗자리가 어떤 건지 확인하려 합니다. 예를 들어 지민이가 가지고 있는 돗자리의 한 변 길이가 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", 사람이 있다면 알파벳 한 글자로 된 값을 갖습니다.

 

2. 출력 예시

 

3. 문제 답안

def solution(mats, park):
    answer = 0
    m = len(park[0])
    n = len(park)
    size = [[0] * m for _ in range(n)] # 2차원 리스트 초기화
    max_size = 0
    
    for i in range(0, n): # 0~5
        for j in range(0, m): # 0~7
            if park[i][j] == "-1":  # 빈 자리
                if i == 0 or j == 0: # 첫 행 또는 첫 열인 경우
                    size[i][j] = 1 # 만들 수 있는 정사각형 크기
                else: # 최소값을 찾아 만들 수 있는 정사각형 크기 계산
                    size[i][j] = min(size[i-1][j], size[i][j-1], size[i-1][j-1]) + 1
    max_size = max(map(max, size)) # 최댓값 찾기
                    
    mats.sort(reverse=True) # 오름차순 정렬
    for m in mats: # 5, 3, 2
        if m <= max_size:
            answer = m
            return answer
    return -1