문제 링크

링크

Code

첫번째 시도

def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

def get_factors(num):
    factors = set()
    for i in range(1, int(num**(1/2))+1):
        if num % i == 0:
            factors.add(i)
            factors.add(num // i)
    return factors

def solution(arrayA, arrayB):
    gcdA = gcd(arrayA[0], arrayA[1])
    for num in arrayA[2:]:
        gcdA = gcd(gcdA, num)
        
    gcdB = gcd(arrayB[0], arrayB[1])
    for num in arrayB[2:]:
        gcdB = gcd(gcdB, num)
        
    factorsA = list(get_factors(gcdA))
    factorsB = list(get_factors(gcdB))
    
    allA = set()
    for num in arrayA:
        allA = allA.union(get_factors(num))
    allB = set()
    for num in arrayB:
        allB = allB.union(get_factors(num))
    
    maxA = 0
    for factor in factorsA:
        if factor in allB:
            continue
        if factor > maxA:
            maxA = factor
    
    maxB = 0
    for factor in factorsB:
        if factor in allA:
            continue
        if factor > maxB:
            maxB = factor
    
    return max([maxA, maxB])

말 그대로 문제를 구현한 것이다.
그러나 시간 초과가 발생했다.

두 번째 시도

dp = dict()

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def get_factors(num):
    global dp
    if num in dp:
        return dp[num]
    
    factors = set()
    for i in range(1, int(num**(1/2)) + 1):
        if num % i == 0:
            factors.add(i)
            factors.add(num // i)
    
    dp[num] = factors
    return factors

def solution(arrayA, arrayB):
    gcdA = gcd(arrayA[0], arrayA[1])
    for num in arrayA[2:]:
        gcdA = gcd(gcdA, num)
    
    gcdB = gcd(arrayB[0], arrayB[1])
    for num in arrayB[2:]:
        gcdB = gcd(gcdB, num)
    
    factorsA = get_factors(gcdA)
    factorsB = get_factors(gcdB)

    allA = set().union(*[get_factors(num) for num in arrayA])
    allB = set().union(*[get_factors(num) for num in arrayB])

    maxA = max((factor for factor in factorsA if factor not in allB), default=0)
    maxB = max((factor for factor in factorsB if factor not in allA), default=0)
    
    return max(maxA, maxB)

메모리제이션을 이용해서 실행 시간을 줄여보려고 했으나 실패했다.

세번째 시도

dp = dict()

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def get_factors(num):
    global dp
    if num in dp.keys():
        return dp[num]
    else:
        factors = set()
        for i in range(1, int(num**(1/2))+1):
            if num % i == 0:
                factors.add(i)
                factors.add(num // i)
        dp[num] = factors
        return factors

def solution(arrayA, arrayB):
    # gcdA와 gcdB 계산 최적화
    gcdA = arrayA[0]
    for num in arrayA[1:]:
        gcdA = gcd(gcdA, num)
    
    gcdB = arrayB[0]
    for num in arrayB[1:]:
        gcdB = gcd(gcdB, num)
        
    factorsA = get_factors(gcdA)
    factorsB = get_factors(gcdB)
    
    # allA와 allB 계산 최적화
    allA = set().union(*[get_factors(num) for num in arrayA])
    allB = set().union(*[get_factors(num) for num in arrayB])

    maxA = max((factor for factor in factorsA if factor not in allB), default=0)
    maxB = max((factor for factor in factorsB if factor not in allA), default=0)
    
    return max(maxA, maxB)

시간을 좀 더 줄여보고자 분할 정복 방식을 적용했다.
메모리제이션과 함께 사용하면 좀 더 시간을 줄여볼 수 있지 않을까 생각했다.
그러나 실패했다.

네번째 시도

from functools import reduce

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def solution(arrayA, arrayB):
    arrayA, arrayB = list(set(arrayA)), list(set(arrayB))
    findGCD = lambda array : reduce(lambda acc, cur : gcd(acc, cur), array, 0)
    checkGCD = lambda array, GCD : GCD if all(e % GCD != 0 for e in array) else 0
    gcdA, gcdB = checkGCD(arrayB, findGCD(arrayA)), checkGCD(arrayA, findGCD(arrayB))
    return 0 if not (gcdA or gcdB) else max(gcdA, gcdB)

이때부턴 포기하고 다른 코드를 참고했다.

소감

정말 정말 어려웠던 문제다.
그리고 내가 놓친 것은 크게 두 가지이다.

1. lambda 함수 사용하기
2. comprehention 사용하기
3. reduce 사용하기!!!

reduce는 정말 중요한 함수이다.
특히 입력값이 클 때 빠르게 연산할 수 있도록 도와준다.
c로 구현되었기 때문에 python loop로 구현된 함수보다 빠르다.

그리고 조건을 함수화 시키는 것에 실패했다.
구현은 가능했지만 시간 초과가 발생했고, 결론적으로는 함수형 프로그래밍을 이용해서 실행 시간을 줄였어야 했다.

사고의 흐름

1. 특정 알고리즘을 적용해야 하는가? -> 그렇지 않다. 보이지 않는다.
2. 그리디인가? -> 오름차순 또는 내림차순에 의해서 문제가 풀릴 실마리가 보이지 않는다. 아니다.
3. 구현하자.
4. 규칙을 찾아야 한다.
   1. 작은 케이스에서 규칙을 찾자 -> 귀납추론
   2. 이를 큰 케이스에 적용하자 -> 연역추론
5. 시간 초과가 발생했다.
   1. memorization을 적용하자
   2. 수학적인 빠른 공식을 찾아보자.
   3. (이번에 추가된 방식) 함수형 프로그래밍을 통해 연산 속도를 높여보자

그리고 아래와 같은 조건들을 뽑아낼 수 있다.

1. 집합 내의 모든 수를 나눌 수 있다. -> 최대공약수
2. 집합 내의 모든 수를 나눌 수 없다. -> 집합 내에 어떤 원소는 다른 집합의 최대공약수로 나눠진다.

정수론 알고리즘

def GreatestCommonDivisor(a, b): # 최대공약수(유클리드 호제법) 알고리즘, O(log(min(a, b)))
	while b != 0:
    	a, b = b, a % b
    return a
    
def LeastCommonMultiple(a, b): # 최소 공배수 알고리즘, O(log(min(a, b)))
	return abs(a * b) // GCD(a, b)
    
def get_factors(num): # 약수 구하기, O(root(n))
	factors = set()
	for i in range(1, int(num**(1/2))+1):
    	if num % i == 0:
        	factors.add(i)
            factors.add(num // i)
    return factors

def prime_factors(num): # 소인수분해 알고리즘, O(root(n))
	factors = []
    i = 2
    while i <= num:
    	if num % i == 0:
        	factors.append(i)
            num = num // i
        else:
        	i += 1
    return factors