[Programmers] 숫자 카드 나누기(Python, JavaScript)

문제

요약

arrayA는 다 나눌 수 있는데 arrayB는 못 나누거나 arrayB는 다 나눌 수 있는데 arrayA는 못나누는 수 중에 최댓값을 구하시오.

 

출처

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

프로그래머스

풀이

각 배열의 최대공약수를 구해서 최대공약수의 약수들이 상대 배열의 값을 못나누는지 확인한다.

두 배열 모두 공약수를 가질 수 있고, 상대 배열을 나눌 수도 있으므로 값의 최댓값을 반환해준다.

 

Python

import math

def getGcd(a, array):
    for i in range(1, len(array)):
        a = math.gcd(a, array[i])
    
    return a if a!=1 else 0

def getDivisor(n):
    divisorsList = []

    for i in range(1, int(n**(1/2)) + 1):
        if (n % i == 0):
            divisorsList.append(i) 
            if ((i**2) != n): 
                divisorsList.append(n // i)

    divisorsList.sort(reverse=True)
    return divisorsList

def sol(lst, arr):
    for i in lst:
        for j in arr:
            if j % i == 0:
                break
        else:
            return i
    return 0

def solution(arrayA, arrayB):
    answer = []
    a = getGcd(arrayA[0], arrayA)
    if a:
        lst = getDivisor(a)
        ra = sol(lst, arrayB)
        answer.append(ra)
    
    b = getGcd(arrayB[0], arrayB)
    if b:
        lst = getDivisor(b)
        rb = sol(lst, arrayA)
        answer.append(rb)
        
    return max(answer) if answer else 0

 

 

JavaScript

let gcd = (num1, num2) => {
    while(num2 > 0){
        let r = num1 % num2;
        num1 = num2;
        num2 = r;
    } 

    return num1;
}

let getGcd = (t, array) => {
    for (let i = 1; i < array.length; i++){
        t = gcd(t, array[i])
    }
    
    return t==1 ? 0 : t
}

let getDivisors = (n) => {
    lst = []
    
    for (let i = 1; i < Math.trunc(n**(1/2)); i++){
        if (n % i == 0){
            lst.push(i)
            if (i ** 2 != n){
                lst.push(n/i)
            }
        }
    }
    
    lst = lst.sort((a,b) => a-b).reverse()    
    return lst
}

let test = (arr, nums) => {
    for (const ar of arr){
        let check = true
        for (const num of nums){
            if (num % ar == 0){
                    check = false
                    break
                }
            }
        
        if (check==true){
            return ar
        }
    }
    return 0
}

function solution(arrayA, arrayB) {
    let answer = [];
    
    const a = getGcd(arrayA[0], arrayA)
    if (a>0){
        const lstA = getDivisors(a)
        const resultA = test(lstA, arrayB)
        answer.push(resultA)
    }
    
    const b = getGcd(arrayB[0], arrayB)
    if (b>0){
        const lstB = getDivisors(b)
        const resultB = test(lstB, arrayA)
        answer.push(resultB)
    }
    
    return answer.length > 0 ? Math.max.apply(null, answer) : 0
}