완전탐색 - 카펫 (Lv.2)

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

 

이 문제를 풀기에 앞서 약수 구하는 알고리즘에 대한 아이디어가 필요했다.

하나하나 확인해보는 방법이 있겠지만 이것보다 좀 더 빠르게 약수를 찾는 방법을 찾고 싶었다. 

그래서 다른 사람의 코드를 확인해본 결과

예를들어, 16이라는 숫자의 약수를 구한다하면 [1, 16], [2, 8], [4, 4] 쌍이되고

[1, 2, 4, 4, 8, 16]으로 16**(1/2)이 약수쌍 중에서 가장 큰(1, 2, 4 중에서) 값이 된다. 

즉, 1부터 16까지 모든 수를 보는게 아니라 약수는 쌍으로 이뤄지므로 최대 16**(1/2) 까지만 봐도 약수는 찾을수 있다.

이 아이디어를 가지고 makeAliQuot(n) 함수를 만들었다.

 

 

<My Source Code 1>

import math
def makeAliquot(n):
    result = []
    for i in range(1, int(math.sqrt(n))+1):
        a = []
        if n%i == 0:
        # 약수 = [i, n//i]
        # n = i*(n//i)
            a.append(i)
            a.append(n//i)
        result.append(a)
    return result

def solution(brown, yellow):
    yelN = makeAliquot(yellow)
    print(yelN)
    for yelSet in yelN:
        if brown == yelSet[0]*2 + yelSet[1]*2 + 4:
            return [yelSet[1]+2, yelSet[0]+2]

통과하거나 런타임에러가 났다.

그럼 이 코드는 효율성 문제를 해결해야 만점을 받을 수 있다는 말이다.

 

<My Source Code 1>

import math
def makeAliquot(n):
    result = []
    for i in range(1, int(math.sqrt(n))+1):
        a = []
        if n%i == 0:
            a.append(i)
            a.append(n//i)
            # 이부분 수정
            result.append(a)
    return result

def solution(brown, yellow):
    yelN = makeAliquot(yellow)
    for yelSet in yelN:
        if brown == (yelSet[0]*2 + yelSet[1]*2 + 4):
            return [yelSet[1]+2, yelSet[0]+2]

그래서 for문쪽을 집중적으로 우선 보았는데, 하나 오류를 범했던 것이 있었다. 

바로 result.append(a)부분을 if문 밖에서 실행시킨 것이다. 

그럼 매번 append가 되기 때문에 런타임 에러가 날 수 밖에 없었던 것이다. 

 

아무튼 알고리즘을 짤때 이런 세세한것도 잘 고려를 해야함을 다시 한번 되새기게 되었다.