[JAVA] Pro 숫자 카드 나누기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/135807?language=java 

프로그래머스

코드

class Solution {
    // 유클리드 호제법
    public int gcd(int a, int b){
        int r;
        while(b!=0){
            r=a%b;
            a=b;
            b=r;
        }
        return a;
    }
    
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        
        int tempA=arrayA[0];
        
        // arrayA의 최대공약수
        for(int i=1; i<arrayA.length; i++){
            tempA=gcd(tempA,arrayA[i]);
        }
        
        int tempB=arrayB[0];
        
        // arrayB의 최대공약수
        for(int i=1; i<arrayB.length; i++){
            tempB=gcd(tempB,arrayB[i]);
        }
        
        int countA=0;
        for(int i=0; i<arrayB.length; i++){
            if(arrayB[i]%tempA==0) countA++;
        }
        
        // arrayB가 가진 숫자 중 하나라도 나눌 수 없으면 answer갱신
        if(countA==0) answer=Math.max(answer, tempA);
        
        int countB=0;
        for(int i=0; i<arrayA.length; i++){
            if(arrayA[i]%tempB==0) countB++;
        }
        
        // arrayA가 가진 숫자 중 하나라도 나눌 수 없으면 answer갱신
        if(countB==0) answer=Math.max(answer, tempB);
        
        return answer;
    }
}

시간복잡도

array.length=n 일 때, O(nlogn)

 

어려웠던 점

arrayA의 최대 공약수가 6일 때, arrayB가 가진 카드가 하나라도 6으로 나누어지면 6의 약수인 2,3으로도 나누어지기 때문에 최대공약수만 비교해보면 된다.