[pro] 프로그래머스 level2 135807 숫자 카드 나누기 (Java) - 시뮬레이션

[문제]

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

프로그래머스

 

[풀이]

arrayA의 최대공약수를 구한 후 arrayB를 나눌 수 없는지 확인한다. 마찬가지로 arrayB의 최대공약수를 구하고, arrayA를 나눌 수 없는지 확인한다. 그 중 더 큰 수가 정답이 된다. 

최대공약수의 약수들에 대해서도 확인해야 하는 것이 아닌가? 라는 생각에 빠져서 조금 헤매었다. 결과적으로는 최대공약수에 대해서만 비교를 해주면 된다. 예를 들어, arrayA의 최대공약수가 72이고 arrayB에 72로 나눌 수 있는 수가 있다면 당연히 72의 약수로도 나누어질 것이므로 정답이 될 수 없다. 만약 72로는 안나누어지지만 72의 약수인 36으로 나누어지는 수가 arrayB에 있다면, 나눌 수 없는 수를 찾고 있으므로 역시 상관이 없다.  

 

최대공약수는 유클리드 호제법을 이용해 구해준다.

 

[코드]

 

import java.util.*;

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        //주어진 조건을 만족하는 가장 큰 양의 정수 a를 return
        
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);
        
        int gcdA = arrayA[0];
        int gcdB = arrayB[0];
        
        //최대 공약수 구하기
        for(int i=1; i<arrayA.length; i++){
            gcdA = gcd(arrayA[i], gcdA);
            gcdB = gcd(arrayB[i], gcdB);
        }
        
        //나눌 수 없는지 확인
        if(!canDivide(arrayB, gcdA)){
            answer = Math.max(answer, gcdA);
        }
        
        if(!canDivide(arrayA, gcdB)){
            answer = Math.max(answer, gcdB);
        }
        
        
        return answer;
    }
    
    public static int gcd(int a, int b){
        if(b==0) return a;
        else return gcd(b, a%b);
    }
    
    public static boolean canDivide(int[] array, int gcd){
        for(int num:array){
            if(num%gcd==0){
                return true;
            }
        }
        return false;
    }
}