[프로그래머스] 카펫. 소인수분해는 소수를 구해야 한다는 고정관념.

부끄럽지만 원래 코드

def solution(brown, yellow):
    MAX = int(yellow**0.5)
    isPrime = [True]*(MAX+1)
    prime = []
    isPrime[0],isPrime[1] = False,False
    for i in range(2,MAX):
        if(isPrime[i]):
            prime.append(i)
            for k in range(2*i,MAX+1,i):
                isPrime[k]=False
		
    m = 1
    n = yellow
    while(yellow>2):
        for p in prime:
            if(yellow%p==0):
                m*=p
                n//=p
                break
        if(2*(m+n)+4==brown):
            break
    if n<m:
        n,m=m,n
    return [n+2,m+2]

• 소인수 분해는 반드시 소수로 해야한다는 생각에 에라토스테네스의 체로 소수를 먼저 구하고 계산하는 모습이다.
• 아래 코드와 비교하면 알겠지만 속도는 처참하다.
• 원인 모르게 틀리기도 한다 ( test case 3)

개선 코드

def solution(brown, yellow):
    for height in range(1, int(yellow ** 0.5) + 1):
        if yellow % height == 0:
            width = yellow // height
            if 2 * (width + height) + 4 == brown:
                return [width + 2, height + 2]

• 일단은 소인수 분해가 아니다.
• 언뜻 보면 소수가 아닌 숫자도 나누기 때문에 오래 걸릴 것 같지만, 어차피 prime 구할 때 반복적으로 하는 로직이기 때문이 이게 훨씬 빠르다.

반성

• 고정 관념을 버리자!
• 소인수 분해를 해야될 것 같은 경우에는, 직접 구현하는 것보다는 작은 숫자부터 그냥 나누는 게 빠를 수도 있다.

번외

• 사실 근의 공식으로 풀었다.

def solution(brown, yellow):
    bp = brown-4
    n = (bp + int((bp**2-16*yellow)**0.5))//4
    m = (bp - int((bp**2-16*yellow)**0.5))//4
    return [n+2,m+2]