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

숫자 카드 나누기

프로그래머스

 

• 내 풀이
  • 최대공약수(GCD)를 활용한 문제 해결 아이디어
    • 배열 A 전체를 나눌 수 있는 자연수는 GCD(A)의 약수뿐이다
    • GCD(A)가 배열 B의 어떤 원소도 나누지 못한다면, GCD(A)는 유효한 후보가 된다
    • 반대로 GCD(B)가 배열 A의 어떤 원소도 나누지 못한다면, GCD(B)도 유효한 후보가 된다
    • 두 경우 모두 확인하여 가장 큰 값을 선택하면 된다
  • 시간복잡도 분석
    • GCD 계산: O(N log M)
    • 배수 여부 검사: O(N)
    • 전체 시간복잡도: O(N log M)
      • N: 배열의 길이 (최대 500,000)
      • M: 배열의 원소 크기 (최대 100,000,000)
        • log M은 log₂(100,000,000) ≈ 27 정도이므로
        • 전체 연산량은 약 500,000 × 27 = 약 13,500,000회로 제한 내에서 충분히 처리 가능

from math import gcd

def solution(arrayA, arrayB):
    answer = 0
    
    a,b=max(arrayA), max(arrayB)
    for ar, br in zip(arrayA,arrayB):
        a=gcd(a,ar)
        b=gcd(b,br)

    for ar, br in zip(arrayA,arrayB):
        if br%a==0:
            a=1
        if ar%b==0:
            b=1

    answer=max(a,b)
    if answer==1:
        answer=0
    
    return answer