[프로그래머스] 135807 숫자 카드 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/135807

숫자 카드 뭉치 두 개가 있는데, 각 뭉치의 공약수 중에서 다른 뭉치의 서로소가 되는 숫자들 중 최대값을 구하는 문제이다.

처음에는 최대공약수를 구해야하는가 싶어서 구하는 함수 만들었는데 만들다 보니까 각 뭉치의 길이가 50만까지 된다길래 다른 방법을 생각했다.

어차피 공약수니까 각 뭉치의 가장 작은 숫자는 넘지 못할 것이기에 가장 작은 숫자 먼저 공략했다.
가장 작은 수의 약수를 구한 후 내림차순으로 정렬했다. 약수는 카드뭉치로 가져와서 모든 숫자와 비교하면서 공약수를 구했다.

구한 공약수는 다른 카드뭉치와 비교하면서 서로소가 되는 가장 큰 수를 구했다. 만약 서로소가 되는 수가 없으면 0을 반환하게 했다.

def getD(n):
    i = 1
    
    ds = []
    while i < n ** (0.5):
        if n % i == 0:
            ds.append(i)
            ds.append(n // i)
        i += 1
            
    ds.sort(reverse = True)
    return ds

def findCD(arr, ds):
    cd = []
    for d in ds:
        chk = True
        for a in arr:
            if a % d:
                chk = False
                break
        if chk:
            cd.append(d)
    return cd

def findNotGCD(arr, cd):
    for c in cd:
        chk = True
        for a in arr:
            if a % c == 0:
                chk = False
                break
        if chk:
            return c
    return 0

def solution(arrayA, arrayB):
    da = getD(min(arrayA))
    db = getD(min(arrayB))
    
    cda = findCD(arrayA, da)
    cdb = findCD(arrayB, db)
    
    ansA = findNotGCD(arrayA, cdb)
    ansB = findNotGCD(arrayB, cda)
    
    return max(ansA, ansB)

처음에는 이렇게 코드 짜고 돌아갈 지 말지 긴가민가 했다. 아무래도 카드의 개수가 50만이고, 숫자 범위도 1억까지라서 2중 for문 코드라서 불안했다.
GPT한테 1억 이하의 숫자 중 약수가 가장 많은 숫자의 약수 개수를 알려달라고 하니까 최대 64개라고 하길래 비교하는 경우의 수는 최대 64 * 50만이겠구나 싶어 용기를 얻고 제출했고 통과했다.