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

링크

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

프로그래머스

 

설명

문제는 A 배열 안에서는 나눌 수 있고, B에서는 나눌 수 없는 어떤 수 N1 과

B 배열 안에서 나눌 수 있고, B에서는 나눌 수 없는 어떤 수 N2가 존재할 때, 해당 값의 최대 값을 구하는 문제입니다.

 

해당 문제는 A 또는 B 배열에서 최대 공약수를 구하고 반대편 배열에서 존재하지 않는 지 확인하는 것으로 풀 수 있습니다.

두 배열 모두에 존재한다면 더 큰 값을 반환하면 됩니다.

 

최대 공약수를 구하면 왜 되는 것인가에 대한 고민을 해 보았습니다.

 

A 배열에서 존재하는 최대 공약수를 구하면 모두 최대 공약수의 약수로 존재합니다.
(ex. 2,3,5 의 약수가 존재한다면 최대공약수는 30)

A의 최대 공약수가 B에 존재할 경우에는 문제의 조건을 만족할 수 없습니다.
(조건 : B 배열의 약수로 존재하지 않아야한다.)

 

고민했던 경우입니다.

 ex 처럼 만약에 최대공약수가 30이라고 할 때 30의 배수는 존재하지않는다면 약수로 존재하는 것은 신경쓰지 않아도 됩니다.

[30, 60], [5, 15] => 30 (5는 안되는 경우이지만 신경쓰지 않아도 됩니다.)

 

 

 

풀이

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        int gcdA = getGcd(arrayA);
        int gcdB = getGcd(arrayB);
        
        if (cannotDivide(gcdA, arrayB)) {
            answer = Math.max(answer, gcdA);
        }
        
        if (cannotDivide(gcdB, arrayA)) {
            answer = Math.max(answer, gcdB);
        }
        
        return answer;
    }
    
    private int getGcd(int[] array) {
        int a = array[0];
        for (int i=1; i<array.length; i++) {
            int b = array[i];
            while (b > 0) {
                int r = a % b;
                a = b;
                b = r;
            }
        }
        
        return a;
    }
    
    private boolean cannotDivide(int gcd, int[] array) {
        for (int i=0; i<array.length; i++) {
            if (array[i] % gcd == 0) {
                return false;
            }
        }
            
        return true;
    }
}​