[프로그래머스] [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", 사람이 있다면 알파벳 한 글자로 된 값을 갖습니다.
    
    
    

📝 코드

def can_place_mat(park, x, y, size):
    for i in range(size):
        for j in range(size):
            # park의 경계를 넘어가거나 '-1'이 아닌 경우
            if x + i >= len(park) or y + j >= len(park[0]) or park[x + i][y + j] != '-1':
                return False
    return True

def solution(mats, park):
    for i in range(len(park)):
        print(type(park[i]))
        park[i] = list(park[i])  # 문자열을 리스트로 변환 -> 효율성 개선 

    # mats를 내림차순으로 정렬하여 가장 큰 돗자리부터 시도
    mats.sort(reverse=True)

    for size in mats:
        for i in range(len(park)):
            for j in range(len(park[0])):
                if can_place_mat(park, i, j, size):
                    return size  # 가장 큰 돗자리 크기 반환

    return -1  # 아무것도 깔 수 없는 경우

 

코드의 주요 로직

• 특정 크기의 돗자리를 공원에 깔 수 있는지를 확인하고, 가능한 위치를 검사하여 가장 큰 돗자리(정사작형)의 길이를 반환하는 문제

1. mats 정렬하기 : mats를 내림차순으로 정렬하여 큰 돗자리부터 시도한다.

2. 공원 탐색 : 공원의 모든 위치를 탐색하고, 함수를 호출하여 돗자리를 놓을 수 있는지 확인한다.

• 돗자리가 공원의 경계를 넘어가지 않는다.
• 해당 위치의 값이 -1이어야 한다.

3. 돗자리 크기 반환 : 돗자리를 놓을 수 있는 위치를 찾으면 반환하고, 놓을 수 없다면 -1을 반환한다.