숫자 카드 나누기

문제

철수와 영희가 각각 N장씩 숫자 카드 배열을 가지고 있습니다. 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a를 구하는 문제입니다.

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

• 입력: 철수가 가진 카드 배열 arrayA, 영희가 가진 카드 배열 arrayB (각 배열의 길이는 1 이상 500,000 이하, 원소의 크기는 1 이상 100,000,000 이하)
• 출력: 조건을 만족하는 가장 큰 양의 정수 a (조건을 만족하는 정수가 없다면 0 반환)

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

풀이: 최대공약수(GCD)를 활용한 최적 탐색

모든 카드를 나눌 수 있는 가장 큰 수는 그 카드들에 적힌 숫자들의 최대공약수(GCD)입니다. 따라서 1부터 순차적으로 탐색하는 것이 아니라, 최대공약수를 먼저 구한 뒤 반대편 배열을 나눌 수 없는지 검증합니다.

• 최대공약수 도출: 철수의 배열 arrayA의 모든 원소에 대한 최대공약수(gcdA)와 영희의 배열 arrayB의 모든 원소에 대한 최대공약수(gcdB)를 구합니다. 여러 수의 최대공약수는 앞에서부터 두 수의 최대공약수를 누적해서 구하는 방식으로 찾을 수 있습니다.
• 조건 검증 (check 메서드):
  • gcdA가 arrayB의 원소 중 단 하나라도 나누어 떨어지게 하는지 검사합니다. 모두 나눌 수 없다면 이 값은 정답 후보가 됩니다.
  • 마찬가지로 gcdB가 arrayA의 원소를 하나라도 나눌 수 있는지 검사합니다.
  • 이때 검사하려는 최대공약수가 1인 경우, 1은 모든 수를 나눌 수 있으므로 검사할 필요 없이 무조건 조건을 만족하지 못합니다(false 반환).
• 최댓값 반환: 두 정답 후보 중 더 큰 값을 반환합니다. 만약 두 경우 모두 조건을 만족하지 못해 후보가 0이라면, 자연스럽게 0이 반환됩니다.

코드

import java.util.*;

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int gcdA = arrayA[0];
        int gcdB = arrayB[0];
        
        // 1. 각 배열의 모든 원소를 나눌 수 있는 최대공약수 구하기
        for (int i = 1; i < arrayA.length; i++) {
            gcdA = gcd(gcdA, arrayA[i]);
            gcdB = gcd(gcdB, arrayB[i]);
        }
        
        // 2. 서로의 배열을 나눌 수 없는지 확인
        int ansA = 0;
        if (check(arrayB, gcdA)) ansA = gcdA;
        
        int ansB = 0;
        if (check(arrayA, gcdB)) ansB = gcdB;
        
        // 3. 조건을 만족하는 값 중 최댓값 반환
        return Math.max(ansA, ansB);
    }
    
    // 유클리드 호제법을 이용한 최대공약수 계산
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    
    // 배열의 어떤 숫자도 주어진 수로 나누어 떨어지지 않는지 판별
    boolean check(int[] arr, int gcd) {
        if (gcd == 1) return false;
        
        for (int n : arr) {
            if (n % gcd == 0)
                return false;
        }
        
        return true;
    }    
}

알고리즘 분류

수학 (Mathematics), 유클리드 호제법 (Euclidean Algorithm), 최대공약수 (GCD)