[프로그래머스] Lv.1 공원 (파이썬)

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 solution(mats, park):
    vacant = []
    for i in range(len(park)):  #세로 6번 반복
        for j in range(len(park[i])):  #가로 8번 반복
            if park[i][j] == "-1":
                vacant.append([i, j])
    pos_mat = [1]
    dx, dy = 1, 1
    for k in range(len(vacant)):
        x, y = vacant[k]
        while True:
            if [x+dx, y] in vacant:
                if [x, y+dy] in vacant:
                    if [x+dx, y+dy] in vacant:
                        pos_mat.append(dx+1)
                        dx += 1
                        dy += 1
            break
    answer = []
    for i in mats:
        if i in pos_mat:
            answer.append(i)
    return max(answer)

 

1트. # 정확도 30.00 코드

대충 생각해본 로직은 일단 빈자리 좌표들을 모아놓은 vacant 리스트를 만들고 그 안에서 순회하면서 +1, +2, +3을 가로. 세로로 모두 해줬을 때 그 값들이 vacant 리스트 안에 다 들어가있으면 그 길이를 pos_mat에 저장한 다음 mats값들이랑 비교해서 가능한 값 뽑아내는 거였음.

근데...! 일단 다시 보니 말도 안되는 코드이긴 하당  k 반복문 while문 다 필요 없는데 왜썼지 암튼.

고민고민하다가 (1시간동안) 힌트라도 얻고자 gpt의 도움을 살짝 받았다.

---

def solution(mats, park):
    vacant = []
    for i in range(len(park)):  #세로 6번 반복
        for j in range(len(park[i])):  #가로 8번 반복
            if park[i][j] == "-1":
                vacant.append([i, j])
                
    pos_mat = [1]
    position = 1
    while position < min(len(park), len(park[0])):
        for x, y in vacant:
            is_square = True
            for dx in range(position+1):
                for dy in range(position+1):
                    if [x+dx, y+dy] not in vacant:
                        is_square = False
                        break
                if not is_square:
                    break
            if is_square:
                pos_mat.append(position+1)
        position += 1
    
    answer = [i for i in mats if i in set(pos_mat)]
    return max(answer)

 

2트. # 런타임에러, 시간초과 -> 70.00점

반복문 두개를 한꺼번에 빠져나오고 싶을 때 (조건 불충족 시) 어떻게 해야할까 정말 고민했는데 flag변수를 사용하면 된다는 것을 배웠다.

예를 들어 can_~~ = True 이렇게 하나 설정해놓고 이걸로 boolean을 설정해주면서 활용하면 됨!

좀 맞나 싶었더니 런타임에러랑 시간초과가 ㅠㅠ

---

def solution(mats, park):
    vacant = set()
    for i in range(len(park)):  #세로 6번 반복
        for j in range(len(park[i])):  #가로 8번 반복
            if park[i][j] == "-1":
                vacant.add((i, j))
                
    pos_mat = {1}
    position = 1
    while position < min(len(park), len(park[0])):
        new_vacant = set()
        for x, y in vacant:
            is_square = True
            for dx in range(position+1):
                for dy in range(position+1):
                    if (x+dx, y+dy) not in vacant:
                        is_square = False
                        break
                if not is_square:
                    break
            if is_square:
                pos_mat.add(position+1)
            else:
                new_vacant.add((x, y))

        position += 1
    
    answer = [i for i in mats if i in pos_mat]
    return max(answer)

 

3트. # 튜플, set 사용해서 시간초과는 잡았지만 런타임 에러는 해결 x

도대체 !!! 런타임 에러가 왜 뜨는지 모르겠음... 

그치만 튜플과 set을 사용하면 시간복잡도가 줄어든다는 것을 배울 수 있었다. 튜플과 set에 요소를 추가할때는 append가 아니라 add인 것도 배울 수 있었음.

---

def solution(mats, park):
    mats.sort(reverse=True)
    for size in mats:
        for x in range(len(park)):
            for y in range(len(park[0])):
                if x+size > len(park) or y+size > len(park[0]): #공원 크기 안 넘어가게
                    continue
                
                can_place = True
                for i in range(size):
                    for j in range(size):
                        if park[x+i][y+j] != "-1": #이미 다른 돗자리가 있으면
                            can_place = False
                            break
                        if not can_place:
                            break
                if can_place:
                    return size
    return -1

 

4트. # 방향성을 뜯어고쳤다. 나의 로직은 실패한 것임.

도저히 런타임에러를 못잡겠어서 지피티와 손을 잡았다. 진짜 천재같아 ...(내가 바보인거겠지만)

돗자리부터 접근하니.. 반복도 훨씬 줄어들고 간단하고 간결하고 단순하게 생각하는 게 가능해졌다.

1. 우선 큰 돗자리부터 검사를 해줄 거라 sort 를 해줬음

2. 일단 범위가 공원의 크기를 넘어가지 않도록 검사해줌

3. 그 다음 순회하면서(범위를 넓혀가면서) 돗자리가 없는 부분에 mat가 다 커버할 수 있는지를 확인.

 

 

한줄평: 최근에 푼 문제 중 내 힘으로 풀려고 가장 오랜 시간을 쏟은 문제... 해결은 못했지만 배운 것은 많았다 ㅠㅠ