[Algorithm] Programmers :: 숫자 카드 나누기

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

프로그래머스

int GetGCD(int a, int b)
{
    int maxNum = max(a, b);
    int minNum = min(a, b);
 
    while (maxNum % minNum != 0)
    {
        int temp = maxNum % minNum;
        maxNum = minNum;
        minNum = temp;
    }
 
    return minNum;
}
 
int solution(vector<int> arrayA, vector<int> arrayB) 
{
    int answer = 0;
 
    int aGCD = arrayA[0];
    int bGCD = arrayB[0];
 
    for (int i = 1; i < arrayA.size(); ++i)
    {
        aGCD = GetGCD(aGCD, arrayA[i]);
    }
 
    bool isCheck = false;
    for (int i = 0; i < arrayB.size(); ++i)
    {
        if (arrayB[i] % aGCD == 0) // 나뉘면 안됨..
        {
            isCheck = true;
            break;
        }
    }
 
    if (isCheck) aGCD = 0;
 
    for (int i = 1; i < arrayB.size(); ++i)
    {
        bGCD = GetGCD(bGCD, arrayB[i]);
    }
 
    isCheck = false;
    for (int i = 0; i < arrayA.size(); ++i)
    {
        if (arrayA[i] % bGCD == 0)
        {
            isCheck = true;
            break;
        }
    }
 
    if (isCheck) bGCD = 0;
 
    return max(aGCD, bGCD);
}

최대공약수를 이용해서 푸는 문제다.

문제 설명을 해석하면, 결국 A의 최대공약수를 구한다음 B에서 하나도 안나눠진다면 후보로 뽑고,

그다음 B의 최대공약수를 구한다음 A에서 하나도 안나눠진다면 마찬가지로 후보로 뽑은 후 둘 중 최댓값을 리턴하면 된다.

최대공약수를 구하는 방법으로는 유명한 방법인 유클리드호제법을 사용한다.