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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/135807

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

문제의 핵심은 최대공약수를 구하는 방법과 이를 여러 번 반복시키는 것으로 보인다.

일단 카드에 적힌 숫자를 모두 나눌 수 있는 가장 큰 수는 최대공약수의 정의와도 같다. 이렇게만 하면 1단계 문제일 텐데 또 조금 꼬아본다고 상대의 카드에 적힌 숫자와는 나누어지지 않도록 조건을 두었다.

이렇게 되면 일단 철수의 최대공약수를 구하고 영희의 모든 카드와 한 번씩 나누어 보는 수 밖에 없다.
최대공약수는 유클리드 호제법을 이용해서 계산하겠다.
혹시 모른다면 나무위키에 잘 정리되어 있으니 확인해보도록 하자. https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95#s-3.3.2.2

아무튼 유클리드 호제법의 시간복잡도는 O(logn) 하지만 영희의 카드를 모두 순회해야 하므로 O(n)의 시간 복잡도를 가지는 풀이가 되겠다. 물론 반대의 경우 철수의 카드 또한 순회해야 한다. 하지만 빅오 표기법 상 계수를 표기하지 않으므로 O(n)으로 볼 수 있다.

def solution(arrayA, arrayB):
    gcd_A = arrayA[0]
    for num in arrayA:
        gcd_A = gcd(gcd_A, num)

    result_A = gcd_A
    for num in arrayB:
        if num % gcd_A == 0:
            result_A = gcd_A // gcd(num, gcd_A)
    
    gcd_B = arrayB[0]
    for num in arrayB:
        gcd_B = gcd(gcd_B, num)

    result_B = gcd_B
    for num in arrayA:
        if num % gcd_B == 0:
            result_B = gcd_B // gcd(num, gcd_B)
        
    if result_A > result_B:
        return result_A
    elif result_A == result_B:
        return 0
    else:
        return result_B


def gcd(a, b):
    r = b % a
    if r == 0:
        return a
    return gcd(r, a)

일단 문제를 빨리 풀고 일해야겠다는 생각에 코딩을 했더니 코드의 추상화 수준이 별로 좋아보이지는 않는다. 그래도 1번 반복되는 정도는 직관적으로 이해하기도 좋으니 그냥 올리도록 하겠다.