[Programmers] 숫자 카드 나누기

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

프로그래머스

문제 설명

이 문제는 최대공약수라는 키워드를 떠올리면 빠르게 해결할 수 있다. 문제는 한 쪽의 카드들은 모두 나눌 수 있고 다른 쪽의 카드는 모두 나눌 수 없아야 하는 수 중에 가장 큰 수를 찾는 것이다. 그렇다면 한 쪽의 카드를 모두 나눌 수 있는 수 중 가장 큰 수는 무엇일까? 바로 최대공약수이다. 한 쪽의 최대공약수를 구했으면 그 수를 가지고 다른 쪽의 수를 모두 나누어보면 된다. 그러다 만약 나누어지는 수가 나온다면 그 최대공약수는 조건을 만족하지 못하게 되는 것이다. 이 과정을 양쪽에 수행하면 문제를 해결할 수 있다.

코드

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int gcd = arrayA[0];
        int resultA = 0;
        
        for (int i = 1; i < arrayA.length; i++) {
            gcd = gcd(gcd, arrayA[i]);
        }
        
        resultA = gcd;
        for (int i = 0; i < arrayB.length; i++) {
            if (arrayB[i] % gcd == 0) {
                resultA = 0;
                break;
            }
        }
        
        gcd = arrayB[0];
        int resultB = 0;
        
        for (int i = 1; i < arrayB.length; i++) {
            gcd = gcd(gcd, arrayB[i]);
        }
        
        resultB = gcd;
        for (int i = 0; i < arrayA.length; i++) {
            if (arrayA[i] % gcd == 0) {
                resultB = 0;
                break;
            }
        }
        
        return Math.max(resultA, resultB);
    }
    
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        
        return gcd(b, a % b);
    }
}