On.

---

Algorithm

---

1. 수도코드

0) 문제 유형 파악: 탐색횟수 최대 2005000번 👉 완전 탐색 문제 (O(N)이나 최대 O(N*logN)의 시간복잡도를 가지는 탐색법으로 풀어야함)

1) 주어진 red로 2차원 리스트를 만드려면, red의 약수여야한다.

• 약수 list생성

2) 약수중에 2개를 뽑아서 곱하고, 그 값이 red랑 같은 것만 필터링한다.

• red가 1일 때는 예외처리한다.

3) 필터링된 행렬들에 테두리를 둘러서 칸 개수가 brown과 같으면 다시 한번 필터링한다.

• (sum(행, 열) + 2 ) * 2 == brown

4) 필터링 된 값에 큰 값이 앞으로, 작은 값이 뒤로 하는 리스트 형태로 리턴

• return [큰값, 작은값]

2. 구현코드

• 제한 사항을 간과했다. 탐색하는 횟수가 백만번이 넘어가는데 combinations 함수의 사용과 filter함수 남발.... 결과는 실패

from itertools import combinations

def solution(brown, red):
    if red == 1:
        return [3, 3]
    
    divisor = [i for i in range(1, red+1) if red % i == 0 ]
    red_matrix = list(filter(lambda x: x[0] * x[1] == red, combinations(divisor, 2)))
    answer = list(filter(lambda x: (sum(x) + 2) * 2 == brown, red_matrix))[0]
    x, y = answer
    
    return [y+2, x+2]

3. 수정한 수도코드

1) 전체 칸 개수가 몇개의 행과 열로 이루어졌는지 알아내기 위해 탐색

• borwn + red에서 1씩 감소하며 순회 (for문)
• row가 전체 칸수의 약수면 col 계산: col = 전체칸 // row
• 구해진 row랑 col에서 테두리 만큼 사이즈를 빼서 곱하기
• 그 값이 red와 같으면 return [row, col]

4. 수정한 구현코드

def solution(brown, red):
    all_tile = brown + red
    
    for row in range(all_tile, 2, -1):
        if all_tile % row == 0:
            col = all_tile // row
            if  red == (row-2) * (col-2):
                return [row, col]

---

Off.

---

프론트와 백을 넘나드는 리드 개발자가 되는 그날까지 🔥🔥🔥