[프로그래머스 Lv2, python] - 숫자 카드 나누기

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

프로그래머스

 

def q(array): # 약수들을 다 저장함
    array.sort()
    array_list=[]
    for i in range(2,array[0]+1):
        cnt=0
        for j in array:
            if j%i==0:
                cnt+=1
        if cnt==len(array):
            array_list.append(i)
    return array_list

def comp(A,array): # 서로의 배열을 비교하기
    result=0
    if len(A)==0:
        return 0
    for i in range(len(A)-1,-1,-1):
        for j in array:
            if j%A[i]==0:
                return result
            result=A[i]
        if result!=0:
            return result
    return result

def solution(arrayA, arrayB):
    answer = 0
    a_num,b_num=q(arrayA),q(arrayB)
    answer=max(comp(a_num,arrayB),comp(b_num,arrayA))
    return answer

처음 풀이는 위의 코드였는데 시간초과로 인해 아래의 코드로 수정하였다.

def gcd(a,b): #최대 공약수.유클리드 호제법 사용
    if a%b==0:
        return b
    return gcd(b,a%b)

def gcd_list(a):
    res=a[0]
    for i in a[1:]:
        res=gcd(res,i)
    return res # 최대 공약수

def get_divisors(n): # 약수들 저장 
    divisors = set()
    for i in range(1, int(n**0.5) + 1): 
        if n % i == 0:
            divisors.add(i) # 나눠지는수랑 
            divisors.add(n // i) # 짝인 수도 추가해주기
    divisors=sorted(divisors, reverse=True) # 내림차순으로 저장
    return divisors

def comp(divisors, array):
    for d in divisors:
        if all(num % d != 0 for num in array): # 나누어 떨어지지 않는것
            return d
    return 0

def solution(arrayA, arrayB):
    answer = 0
    li_A,li_B=gcd_list(arrayA),gcd_list(arrayB)
    divisorsA=get_divisors(li_A)
    divisorsB=get_divisors(li_B)
    return max(comp(divisorsA, arrayB), comp(divisorsB, arrayA))