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

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

프로그래머스

 

풀이

돗자리 한변의 크기가 담긴 mats, 공원의 정보 park가 주어질 때 가능한 가장 큰 돗자리를 찾는 문제입니다.

돗자리를 깔 수 없는 경우 -1을 리턴해야 합니다.

 

• 주어진 변수의 크기가 크지 않으므로 조건처리를 하여 완전탐색으로 해결할 수 있습니다.
• 우선 가장 큰 돗자리부터 평가하기 위해 내림차순 정렬합니다.
• 가장 큰 돗자리부터, park의 모든 (행, 열)에서 시작하여 돗자리를 깔아야할 면적에 알파벳이 존재하는지 평가합니다.
• 돗자리를 깔 수 있는지 평가하기 위한 함수 access는 (시작 행, 시작 열) 에서부터 검사해야 할 영역까지 "-1"이 아닌 값이 있는지 확인합니다. 이때, park의 범위를 벗어나지 않도록 주의합니다.
• "-1"이 아닌 경우, 범위를 모두 벗어난 경우가 아니라면 (시작 행, 시작 열)에서 돗자리를 깔 수 있으므로 True를 반환합니다. 

def access(mat, park, st_row, st_col):
    for r in range(st_row, st_row+mat):
        for c in range(st_col, st_col+mat):
            if r < len(park) and c < len(park[0]):
                if park[r][c] != "-1":
                    return False
            else:
                return False
    return True
    
def solution(mats, park):
    answer = 0
    mats.sort(reverse=True)
    
    R = len(park)
    C = len(park[0])
    for mat in mats:
        for r in range(R):
            for c in range(C):
                if access(mat, park, r, c):
                    return mat
    
    return -1