HackerRank/Between Two Sets

arr이 2개 주어진다.

1번째 arr에 담겨있는 숫자들의 공배수들 중 2번째 arr의 가장 작은 값 이하인 녀석들을 num이라 한다면, 2번째 arr에 담겨있는 숫자들을 나머지가 0이 되도록 나눌 수 있는 num의 개수를 세는 문제이다.

예시를 보자면 a=[2,6]이 주어지고 b=[24,36]이 주어진다.

2와 6의 공배수는 6의 배수들이다. 6,12,18,24,30,36.... 이 중 24보다 작은 녀석들은 6,12,18,24 이다.

다시 이 녀석들 중 b의 원소들을 모두 나머지 없이 나눌 수 있는 녀석들은 6,12의 2가지고 return 값은 2가 된다.

공배수니 뭐니 수학적 얘기가 막 나와서 머리가 좀 아픈데, 수학적 얘기들을 치우면 단순한 해결법이 존재한다.

a[마지막] <= number <= b[첫번째] 를 만족하는 모든 수들에 대해서 a원소들의 공배수인지 테스트하고, b원소들의 약수인지 테스트해서 맞으면 count를 증가시키고 이를 반환하면 된다.

효율이 썩 좋지는 않지만, 문제의 난이도가 easy이고 주어지는 set의 범위가 좁은만큼 단순한 풀이로 푸는것을 원하는 것 같다.

int getTotalX(vector<int> a, vector<int> b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    int cnt=0;
    
    //try all numbers a[last] <= num <= b[first]
    for(int i=a[a.size()-1]; i<=*b.begin(); ++i)
    {
        bool chk = false;
        for(int j=0; j<a.size(); ++j)
        {
            if(i%a[j]!=0)
            {
                chk = true;
                break;
            }
        }
        
        if(chk) continue;
        
        chk = false;
        for(int j=0; j<b.size(); ++j)
        {
            if(b[j]%i!=0)
            {
                chk = true;
                break;
            }
        }
        
        if(chk) continue;
        
        cnt++;
    }
    
    //and return count
    return cnt;
}

---

다만, O(n^2)이 맘에 들지 않는다면 다른 방안도 있다. 다만, 중학교 수학을 열심히 했었어야 한다.

a배열의 최소 공배수를 구하고 b배열의 최대 공약수를 구하고, a의 배수들 중 최대 공약수의 약수인 녀석의 수를 구하면 된다.

눈여겨보아야 할 점은, N개의 수들에 대해서 어떻게 gcd, lcm을 구하는가? 이다. 단순하다, 2개의 수에 대해서 구하는 방식을 for 루프 돌려서 모두에 대해 적용시켜서 나온 수를 쓰면 된다.

int gcd(int a, int b)
{
    int c;
    while(b!=0)
    {
        c = a%b;
        a = b;
        b = c;
    }
    
    return a;
}

int lcm(int a, int b)
{
    return a*b / gcd(a, b);
}

int getTotalX(vector<int> a, vector<int> b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    int l = a[0];
    int g = b[0];
    
    for(int i=1; i<a.size(); ++i)
    {
        l = lcm(l, a[i]);    
    }
    
    for(int i=1; i<b.size(); ++i)
    {
        g = gcd(g, b[i]);
    }
    
    int cnt=0;

    for(int i=1; l*i<=g; ++i)
    {
        if(g%(l*i)==0) cnt++;
    }
    
    return cnt;
}