공원(L1)

문제 설명

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

---

입출력 예

mats	park	result
[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

---

입출력 예 설명

입출력 예 #1

• 지문과 동일합니다.

나의 풀이

def solution(mats, park):
    answer = -1
    H=len(park)
    W=len(park[0])
    mats.sort(reverse=True)
    for m in mats:
        for i in range(H-m+1):
            for j in range(W-m+1):
                can=True
                if park[i][j]=='-1':
                    for i2 in range(i,i+m):
                        for j2 in range(j,j+m):
                            if park[i2][j2]!='-1':
                                can=False
                                break
                        if not can:
                            break
                    if can:
                        answer=m
                        return answer
    
    
    return answer

• 완전 탐색으로 풀었다.
• 문제를 봤을 때, Computational cost를 계산해서 어떤 방식으로 풀지 결정하는 것을 연습해야 한다.

다른 사람 풀이

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

• 조금 더 깔끔해 보이긴 한다. 하지만 도중에 멈추지 않기 때문에 내 코드보다 조금 덜 효율적이지만 가독성이 매우 좋다.