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

문제

최대공약수를 구해서, 서로의 배열을 나눌 수 있는지 여부를 구하고 나눌 수 없다면, answer를 나눌 수 있다면, 0을 return 하는 문제이다.

최대공약수를 구할 때 나는 유클리드 호제법을 사용했다.

 

코드

def solution(arrayA, arrayB):
    answer = 0
    if len(arrayA) == 1:
        if arrayA[0] == arrayB[0]:
            return 0
        else:
            return max(arrayA[0], arrayB[0])
    else:
        m1 = 0
        m2 = 0
        gcd1 = gcd(arrayA[0], arrayA[1])
        gcd2 = gcd(arrayB[0], arrayB[1])
        answer = max(m1,m2)
        for i in range(2, len(arrayA)):
            gcd1 = gcd(gcd1, arrayA[i])
            gcd2 = gcd(gcd2, arrayB[i])
        if gcd1 != 1 and canDivide(arrayB, gcd1) == False:
                m1 = gcd1
        if gcd2 != 1 and canDivide(arrayA, gcd2) == False:
                m2 = gcd2
        answer = max(m1,m2)
    return answer

def gcd(a, b):
    
    if b == 0:
        return a
    else:
        if a < b:
            return gcd(a, b % a)
        else:
            return gcd(b, a % b)
        
def canDivide(array, a):
    for i in range(len(array)):
        if array[i] % a == 0:
            return True
    return False
"""
가장 큰 양의 정수 a의 값 구하기
철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도
나눌 수 없는 양의 정수 a
A와 B에 들어있는 약수들 중 겹치지 않고 큰 수
"""