숫자 카드 나누기

숫자 카드 나누기

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

문제

풀이

최대공약수를 이용해서 풀었다.
arrayA = [14, 35, 119], arrayB = [18, 30, 102]라고 하자
1. 파이썬 math에 gcd를 이용해서 각 배열의 최대공약수를 구한다.
=> gcdA = 7, gcdB = 6이 될 것이다.
2. 이제 최대 공약수의 약수를 구한다.
=> arrA = [7, 1] , arrB = [6, 3, 2, 1]
3. 문제 조건에 맞는 최대값을 구한다.
arrA = 7일 때 18, 30, 102 전부 안 나누어 떨어진다. 따라서 7이 최대값이다.

이것을 코드로 나타내면 다음과 같다.
1. arrayA의 최대공약수 gcdA, arrayB의 최대공약수 gcdB를 구하자.

2. 최대공약수를 약수로 바꾸는 함수를 작성한다.
   

3. 문제 조건에 맞는 최대값을 구한다.
   
   만약 나누어 떨어지는 것이 있으면 조건에 맞지 않는 것이다.

import math
def solution(arrayA, arrayB):
    gcdA, gcdB= 0, 0
    arrA, arrB = [], []
    
    def cal(num):
        arr = []
        for i in range(num, 0, -1 ):
            if num % i == 0:
                arr.append(i)
        return arr
    
    for i in range(len(arrayA)):
        if i == 0:
            gcdA = arrayA[i]
            continue
        gcdA = math.gcd(gcdA, arrayA[i])
    
    for i in range(len(arrayB)):
        if i == 0:
            gcdB = arrayB[i]
            continue
        gcdB = math.gcd(gcdB, arrayB[i])
    
    arrA, arrB = cal(gcdA), cal(gcdB)
    
    answer = 0
    
    for eachA in arrA:   
        flg = False
        for eachB in arrayB:
            if eachB % eachA == 0:
                flg = True
                break
        if not flg:
            answer = max(answer, eachA)
    
    for eachB in arrB:   
        flg = False
        for eachA in arrayA:
            if eachA % eachB == 0:
                flg = True
                break
        if not flg:
            answer = max(answer, eachB)
    return answer

결과