숫자 카드 나누기

⭐️
import math

def solution(arrayA, arrayB):
    gcdA, gcdB = arrayA[0], arrayB[0]
    
    # 최대공약수 활용
    for item in arrayA:
        gcdA = math.gcd(gcdA, item)
    for item in arrayB:
        gcdB = math.gcd(gcdB, item)
    
    # 서로의 최대공약수로 검증
    for idx in range(len(arrayA)):
        if arrayA[idx] % gcdB == 0:
            gcdB = 1
        if arrayB[idx] % gcdA == 0:
            gcdA = 1
    
    # 조건에 맞는 답 존재X
    if gcdA == 1 and gcdB == 1:
        return 0
    else:
        return max(gcdA, gcdB)

• 최대공약수로 접근할 생각을 처음에 하지 못했음.

  • 만약 큰 수가 조건을 만족하지 않을 때, 그의 약수도 따져보아야 한다고 생각했기 때문.
  • 그러나, 조금만 더 생각해보면 k로 나누어지는 배열의 수들은 k의 약수들로도 나누어지는 것이 당연하므로 신경쓰지 않아도 된다.

• 참고로, 만약 math gcd 를 못쓴다고 하면 유클리드 알고리즘으로 직접 구현하면 됨.

  def gcd3(p, q):
     while(q):
         p, q = q, p % q
     return p

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges