[프로그래머스] 숫자 카드 나누기 / 자바(Java)

문제

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

프로그래머스

 

---

해설

두 배열의 수들을 중, 한쪽은 모두 나눌 수 있고, 한쪽은 모두 나눌 수 없는 값을 구하는 문제입니다.

한쪽을 모두 나눌 수 있다는 점에서 공약수를 생각했고 그중 가장 큰 양의 정수이므로 최대 공약수를 통해 해결한다는 방향성을 찾았습니다. 

 

1. 각 배열의 최대공약수 구하기

공약수를 구하는 방식으로는 유클리드 호제법을 사용했습니다.

시간복잡도가 O(logN)이므로 긴 범위(500,000)이라도 사용가능했습니다.

 

2. 다른 배열의 최대공약수와 이번 배열의 모든 수를 나누어보기

위에서 구한 최대공약수를 통해 모든 수를 나누고 성공한 경우 가장 큰 수를 answer에 남김니다.

주의점

• 최대공약수를 구하는 적절한 방식

---

코드

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        int gcdA = arrayA[0], gcdB = arrayB[0];
        
        // 각 배열별 최대공약수 구하기
        for(int i=1;i<arrayA.length;i++){
            gcdA = gcd(gcdA,arrayA[i]);
            gcdB = gcd(gcdB,arrayB[i]);
        }
        
        // A의 최대공약수로 B를 나누어보기
        if(!isDivisible(arrayB, gcdA))
            if(answer < gcdA)
                answer = gcdA;
        // B의 최대공약수로 A를 나누어보기
        if(!isDivisible(arrayA, gcdB))
            if(answer < gcdB)
                answer = gcdB;
        return answer;
    }
    
    // 특정 값으로 해당 배열의 값을 모두 나눌수 없는가 확인
    public boolean isDivisible(int[] arr, int input){
        for(int a : arr) if(a % input==0) return true;
        return false;
    }
    
    // 최대공약수 구하기
    public int gcd(int a, int b){
        if(a % b == 0) return b;
        return gcd(b, a % b); 
    }
}