[Python] 프로그래머스 : [PCCE 기출문제] 10번 / 공원 340198, sort, set

 

 

📝 문제

지민이는 다양한 크기의 정사각형 모양 돗자리를 가지고 공원에 소풍을 나왔습니다. 공원에는 이미 돗자리를 깔고 여가를 즐기는 사람들이 많아 지민이가 깔 수 있는 가장 큰 돗자리가 어떤 건지 확인하려 합니다. 예를 들어 지민이가 가지고 있는 돗자리의 한 변 길이가 5, 3, 2 세 종류이고, 사람들이 다음과 같이 앉아 있다면 지민이가 깔 수 있는 가장 큰 돗자리는 3x3 크기입니다.

지민이가 가진 돗자리들의 한 변의 길이들이 담긴 정수 리스트 mats, 현재 공원의 자리 배치도를 의미하는 2차원 문자열 리스트 park가 주어질 때 지민이가 깔 수 있는 가장 큰 돗자리의 한 변 길이를 return 하도록 solution 함수를 완성해 주세요. 아무런 돗자리도 깔 수 없는 경우 -1을 return합니다.

 

🫠 나의 풀이

def solution(mats, park):
    rows = len(park)
    cols = len(park[0])
    max_size = -1

    mats.sort()

    for m in range(len(mats) - 1, -1, -1): # 큰 매트부터 역순으로 조회
        can_place = False

        for i in range(rows - mats[m] + 1): # 매트 배치 가능한 마지막 행 좌표
            for j in range(cols - mats[m] + 1): # 매트 배치 가능한 마지막 열 좌표
                all_minus_one = True

                for x in range(i, i + mats[m]):
                    for y in range(j, j + mats[m]):
                        if park[x][y] != "-1":
                            all_minus_one = False
                            break
                    if not all_minus_one:
                        break

                if all_minus_one: # 모두 빈 공간 "-1" 이라면 배치 가능하다 판단하고 루프 탈출
                    can_place = True
                    break

            if can_place: # 배치 가능하면 탈출
                break

        if can_place: # 배 가능하면 사이즈 저장
            max_size = mats[m]
            break

    return max_size

 

🧞‍♂️ 다른 사람의 풀이

def solution(mats, park):
    mats = sorted(mats, reverse = True)
    M, N = len(park), len(park[0])

    for l in mats:
        startIdxSet = set((i,j) for i in range(M-l+1) for j in range(N-l+1))
        for a, b in startIdxSet:
            ret = set()
            for i in range(a,a+l):
                for j in range(b,b+l):
                    ret.add(park[i][j])
            if ret == {'-1'}:
                return l
    return -1

 

 

 

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

프로그래머스