[HackerRank] Between Two Sets 📌 (여러 수 최대공약수, 최소공배수)

 

문제 

a배열의 최소공배수의 배수이면서 b배열의 최대공약수의 약수인 수(?) 의 개수

 

 

 

 

 

 

내 풀이 

여러 수의 최소공배수, 최대공약수 구하는 방법은 쫌 찾아봤슴다

 

private static int getTotalX(List<Integer> a, List<Integer> b) {

    // a배열의 최소공배수
    int aLCD = a.get(0);
    for(int i=1; i < a.size(); i++) {
        aLCD = LCD(aLCD, a.get(i));
    }

    // b배열의 최대공약수
    int bGCD = b.get(0);
    for(int i=1; i < b.size(); i++) {
        bGCD = GCD(bGCD, b.get(i));
    }

    // a배열의 최소공배수의 배수이면서 b배열의 최대공약수의 약수
    int answer = 0;
    for(int i=1; i<=100; i++) {
        if(i % aLCD == 0 && bGCD % i == 0)
            answer ++;
    }

    return answer;
}

// 최대공약수
public static int GCD(int num1, int num2) {
    if(num1 % num2 == 0) {
        return num2;
    }
    return GCD(num2, num1%num2);
}

// 최소공배수
public static int LCD(int num1, int num2) {
    return num1 * num2 / GCD(num1, num2);
}

 

 

📌 여러 수 최대공약수, 최소공배수 구하기

 

GCD, LCD 함수를 정의했다고 할 때, 

1) 일단 배열의 첫번째 값으로 초기화 

2) 초기화한 값과 i번째 값 비교 (i = 1부터)