[프로그래머스][JAVA]Lv. 2 - 숫자 카드 나누기

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

프로그래머스

두개의 그룹에서 한 그룹의 적힌 모든 숫자를 나눌 수 있고 다른 그룹이 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a를 구하고 구할 수 없다면 0을 출력하는 문제

public int gcd(int a, int b) {
    int r = a % b;
    if (r == 0) return b;
    return gcd(b, r);
}

먼저 유클리드 호제법을 이용하여 배열 arrayA의 최대공약수와 배열 arrayB의 최대공약수를 구해주었다

그리고나서 arrayA의 모든 요소에 arrayB의 최대공약수를 나누어 나머지가 0인 경우 a를 true로, 반대인 경우 b를 true로 하였다

그렇게 a와 b 모두 true가 되는 경우 양의 정수 a를 구할 수 없으므로 0을 출력하였다

그렇지 않은 경우에는 arrayA와 arrayB의 최대공약수 중 더 큰 수를 정답으로 출력하였다

처음에 다른 방식으로 풀었다가 시간초과로 풀지 못하였다 조건에 있는 arrayA 또는 arrayB의 크기가 100,000,000가 될 수 있기 때문이다

그래서 더 간단한 방법으로 풀었더니 통과할 수 있었다

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int maxA = arrayA[0];
        int maxB = arrayB[0];
        boolean a = false;
        boolean b = false;
        for (int i = 0; i < arrayA.length; i++) {
            maxA = gcd(maxA, arrayA[i]);
        }
        for (int i = 0; i < arrayB.length; i++) {
            maxB = gcd(maxB, arrayB[i]);
        }
        for (int i = 0; i < arrayA.length; i++) {
            if (arrayA[i] % maxB == 0) a = true;
        }
        for (int i = 0; i < arrayB.length; i++) {
            if (arrayB[i] % maxA == 0) b = true;
        }
        if (a && b) return 0;
        else return Math.max(maxA, maxB);
    }
    public int gcd(int a, int b) {
        int r = a % b;
        if (r == 0) return b;
        return gcd(b, r);
    }
}