숫자 카드 나누기

문제

풀이

//최대공약수가 다른 배열의 약수가되는지 아닌지 확인한다.
class Solution {
    //최대공약수
    static int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a%b);
    }
    
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        int a = 0;
        int b = 0;
        
        //최대 공약수를 구하고.
        for(int i = 0; i < arrayA.length; i++) {
            int max = Math.max(arrayA[i], a);
            int min = Math.min(arrayA[i], a);
            a = gcd(max, min);
         }
        for(int i = 0; i < arrayB.length; i++) {
            int max = Math.max(arrayB[i], b);
            int min = Math.min(arrayB[i], b);
            b = gcd(max, min);
        }
        
        // 각자의 최대공약수로 다른 배열에 나눠 떨어지면 최대공약수 0으로 만들고 스톱.
        for(int i : arrayB) {
            if(i % a == 0) {
                a = 0;
                break;
            }
        }
        for(int i : arrayA) {
            if(i % b == 0) {
                b = 0;
                break;
            }
        }
        
        answer = Math.max(a,b);
        
        return answer;
    }
}

이 문제 핵심은 자신의 배열은 서로 나누어져야하고, 다른 배열은 그러지 않아야 한다.
A배열에서 가진 최대공약수로 B배열에서 아무요소도 나누어지지않아야한다. 또는 B배열에서 가진 최대공약수로 A배열에서 아무요소도 나누어지지않아야한다는 것이다.
즉 최대공약수를 가진다는 것은 자신의 배열은 서로 나누어 진다는 것.

그래서

1. 각 배열의 최대공약수를 구한다.

   만약에 최대공약수가 0이면, 그 배열은 서로 나누어지지 않은 배열의 경우라고 할 수 있다. 반대편에서 최대공약수를 가지면 문제 조건 성립

2. 각 배열의 최대공약수로 다른 배열에 나누어 떨어지는지 확인한다. 만약에 나누어 떨어지면 최대 공약수를 0으로 만들어버린다. 그 최대공약수는 정답이될수없다.