숫자 카드 나누기 - Pyton, GCD, Reduce

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/135807

프로그래머스

 

 

코드 & 풀이

 

def gcd(num1, num2):
    while num2:
        num1, num2 = num2, num1%num2
    return num1

def find_gcd(nums):
    result = nums[0]
    
    for num in nums[1:]:
        result = gcd(result, num)
        if result == 1:
            break
    return result

def can_divide(nums, gcd_value):
    if gcd_value == 1:
        return 0
    return gcd_value if all(num % gcd_value != 0 for num in nums) else 0

def solution(arrayA, arrayB):
    a_gcd = find_gcd(arrayA)
    b_gcd = find_gcd(arrayB)

    max_gcd_A = can_divide(arrayB, a_gcd)
    max_gcd_B = can_divide(arrayA, b_gcd)

    return max(max_gcd_A, max_gcd_B)

 

GCD

 

즉, 최대 공약수를 구해서

 

다른 리스트가 나눠지는 지 확인하기만 하면 됩니다.

 

가장 큰 조건인 GCD를 구하는 건

 

유클리는 호제법을 활용했습니다.

 

https://fall-in-dream.tistory.com/11

최대 공약수(GCD), 최소 공배수(LCM) 구하기, 유클리드 호제법 - JAVA

 

전에 자바버전으로 올린건데

 

참고하시면 좋을 거 같습니다.

 

from math import gcd
from functools import reduce

def find_gcd(nums):
    return reduce(gcd, nums)

def can_divide(nums, gcd_value):
    if gcd_value == 1:
        return 0
    return gcd_value if all(num % gcd_value != 0 for num in nums) else 0

def solution(arrayA, arrayB):
    a_gcd = find_gcd(arrayA)
    b_gcd = find_gcd(arrayB)

    max_gcd_A = can_divide(arrayB, a_gcd)
    max_gcd_B = can_divide(arrayA, b_gcd)

    return max(max_gcd_A, max_gcd_B)

 

이번에는 라이브러리를 사용한 버전입니다.

 

좀 더 간단해 보이죠?

 

하지만 저는 저 imort를 외울 자신이 없습니다....

 

 

 

다음에 또 봐요