[Python : 프로그래머스] 카펫

문제

https://programmers.co.kr/learn/courses/30/lessons/42842?language=python3

풀이

def solution(brown, yellow):
    total = brown + yellow
    cd = [i for i in range(2,total) if total % i == 0]
    
    if len(cd) % 2 == 0 :
        return [cd[len(cd)//2], cd[len(cd)//2-1]]
    else :
        return [cd[len(cd)//2], cd[len(cd)//2]]

total 은 Brown + Yellow, 즉 넓이를 의미한다.
1과 자신을 제외한 모든 약수들을 구한 다음
그 약수들의 중간 값을 반환하면 가장 정사각형 카펫에 알맞는 가로 세로 길이가 반환된다.

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (55.43ms, 10.2MB)
테스트 4 〉	실패 (0.58ms, 10.2MB)
테스트 5 〉	통과 (1.12ms, 10.2MB)
테스트 6 〉	실패 (18.88ms, 10.1MB)
테스트 7 〉	실패 (70.87ms, 10.2MB)
테스트 8 〉	통과 (56.71ms, 10.2MB)
테스트 9 〉	통과 (69.34ms, 10.2MB)
테스트 10 〉	통과 (81.82ms, 10.2MB)
테스트 11 〉	통과 (0.01ms, 10.2MB)
테스트 12 〉	통과 (0.01ms, 10.2MB)
테스트 13 〉	통과 (0.01ms, 10.1MB)

얼레? 당연히 정답이라 생각했는데
4, 6, 7 테스트 케이스를 통과하지 못한다.
가늠이 안가서 질문 게시판을 돌아봤다.
그러던 중 발견한 내용

ㄱㄱㄱㄱㄱㄱ
ㄱㅇㅇㅇㅇㄱ <- 이 경우로 해결해야 됌
ㄱㄱㄱㄱㄱㄱ

ㄱㄱㄱㄱ
ㄱㅇㅇㄱ <- 이 경우는 통과 못함
ㄱㅇㅇㄱ
ㄱㄱㄱㄱ

‘지문만 읽고 이걸 어찌 알아!!’ 라고 생각했는데,
Input Brown과 값이 일치해야 한다는 걸 뒤늦게 깨달았다.
다시 생각해보자…

Yellow의 배치에 따라 필요한 Brown이 달라진다.
즉, Brown 숫자에 맞춰서 가로세로 길이가 달라질 수 있다.
이 때부터 단순히 블럭배치가 아니라 사각형의 넓이를 이용해 풀어야 하는구나 생각되었다.

Brown + Yellow = row * column  # total extent
Yellow = (row-2)*(column-2)    # yellow extent
----------------------------------------------------------------
Brown = (row * column) - (row * column) + 2(row + column) - 4
Brown = 2(row + column) - 4
(Brown + 4) / 2 = row + column

즉, 제공되는 Brown 개수에 (+4)/2를 해주면
가로와 세로길이의 합을 구할 수 있고,
이 합을 쪼개서 서로 곱한 값이
Brown+Yellow 개수와 일치하면 정답이라고 생각할 수 있다.

def solution(brown, yellow):
    extent = brown + yellow
    x_plus_y = (brown+4)//2
    
    if x_plus_y % 2 == 0 :
        x = x_plus_y // 2
        y = x_plus_y // 2
    else :
        x = x_plus_y // 2 + 1
        y = x_plus_y // 2
    
    for i in range(x_plus_y) :
        if x * y == extent :
            return [x, y]
        x += 1
        y -= 1
    return [x,y]

성공!

더 나은 풀이

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

둘레길이를 이용한 방식이라는데,
개인적으로는 아예 생각을 못했어서 오히려 더 와닿는게 없다.

def solution(brown, red):
    nm = brown + red
    for n in range(1, nm+1):
        if nm%n != 0:
            continue
        m = nm//n
        if (n-2)*(m-2) == red:
            return sorted([n, m], reverse = True)

총 넓이 값을 토대로 반복문을 돌리다가
구한 두 약수-2 끼리의 곱 값이
Yellow 와 개수가 같으면 정답
이렇게 쉽게 접근하는 방법도 있었구나!

import math
def solution(brown, yellow):
    w = ((brown+4)/2 + math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    h = ((brown+4)/2 - math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    return [w,h]

근의공식을 이용한 방법.
아마 내 풀이를 좀더 간결하게 수식으로 풀어냈으면
이렇게 풀어지지 않았을까 생각한다.
내 풀이의 상위호환