[HackerRank]Between Two Sets

Between Two Sets

You will be given two arrays of integers and asked to determine all integers that satisfy the following two conditions:
1. The elements of the first array are all factors of the integer being considered
2. The integer being considered is a factor of all elements of the second array
These numbers are referred to as being between the two arrays. You must determine how many such numbers exist.

CODE

int gcd(int a, int b) { // 최대공약수 구하는 함수
    if (b > a) {
        int temp = b;
        b = a;
        a = temp;
    }
    while (b) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int lcm(int a, int b) { // 최소공배수 구하는 함수
    return a * b / gcd(a, b);
}

int getTotalX(int a_count, int* a, int b_count, int* b) {
    int lcm_a = *a, gcd_b = *b, count = 0;
    //lcm_a : 최소공배수, gcd_b : 최대공약수, count : a의 배수인 동시에 b의 약수인 정수의 개수

    for (int i=0;i<a_count && lcm_a<=100;i++) lcm_a = lcm(*(a+i), lcm_a); //  최소공배수 구하기
    for (int i=0;i<b_count;i++) gcd_b = gcd(*(b+i), gcd_b); // 최대공약수 구하기

    if ((gcd_b == 0) || (lcm_a > 100) || (lcm_a > gcd_b)) return 0;
    // 최대공약수가 0이거나, 최소공배수가 100보다 크거나, 최소공배수가 최대공약수보다 클 때는 0을 반환한다.

    for (int i=lcm_a;i<=gcd_b;i++) { // 최소공배수보다 크거나 같고 최대공약수보다 작거나 같은 수 중에서
        if ((gcd_b%i == 0) && (i%lcm_a == 0)) count++;
        // 그 수가 최대공약수의 약수 (= b의 약수)이고 최소공배수의 배수(= a의 배수)이면 count 증가
    }
    return count;
}

MEMO

문제 해석이 제일 어려웠다. 문맥을 살펴봤을 때 a의 배수인 동시에 b의 약수인 정수의 개수를 구하라는 문제같았다. 나는 최대공약수와 최소공배수를 이용해서 풀고자 하였기 때문에 우선 유클라드 호제법을 이용해서 b의 최대공약수와 a의 최소공배수를 구했다. 최대공약수의 약수 중에서 최소공배수의 배수를 구했다.

문제를 푸는데 test case 1이 자꾸 실패했다. 고민하다가 살펴보니 test case 1은 다음과 같았다.

10 10
100 99 98 97 96 95 94 93 92 91
1 2 3 4 5 6 7 8 9 10

코드가 출력하는 결과를 일일히 확인해보니까 lcm_a가 int형의 범위를 넘어서 문제였다. 따라서 lcm_a가 100보다 작거나 같을 때만 진행될 수 있도록 코드를 수정했다.
int형 범위를 신경쓸 것!