프로그래머스 - 숫자 카드 나누기

문제 링크 ▶︎ 프로그래머스 숫자 카드 나누기

문제 전략

이 문제는 수학 구현 문제이다.

A 카드에서의 최대공약수와 B 카드에서의 최대공약수만 비교하면 된다.
그 이유는 만약 A 카드의 최대공약수가 B 카드 중 하나라도 나누어 떨어지게 된다면 A 카드의 최대공약수의 약수들은 무조건 나누어 떨어진다.
그렇기 때문에 최대공약수들만 비교하면 된다.

각각의 최대공약수가 서로의 카드 중 1개라도 나누어 떨어지면 1로 바꿔버리고 두 카드 모두 1이라면 0을 출력, 아니라면 더 큰 값을 출력한다.

코드

def solution(arrayA, arrayB):
    answer = 0
    
    def gcd_(a,b):
        while b > 0:
            a, b = b, a%b
        return a
    
    def gcd_lst(lst):
        gcd = lst[0]
        for x in lst:
            gcd = gcd_(gcd,x)
        return gcd
    
    gcd_a = gcd_lst(arrayA)
    gcd_b = gcd_lst(arrayB)
    
    for i in range(len(arrayA)):
        if arrayA[i] % gcd_b == 0:
            gcd_b = 1
        if arrayB[i] % gcd_a == 0:
            gcd_a = 1
    
    if gcd_a == 1 and gcd_b == 1:
        answer = 0
    else:
        answer = max(gcd_a,gcd_b)
    
    return answer

개선 사항

① math 라이브러리 안쓰고 gcd 구현을 자주해야할듯.
② 수학 구현 문제도 자주 풀어봐야할듯.