[프로그래머스] Lv.2 숫자 카드 나누기 (Java)

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

프로그래머스

 

문제 설명

A와 B가 숫자카드를 절반씩 나눠 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수를 구합니다.

1. A가 가진 모든 숫자를 나눌 수 있고, B가 가진 모든 숫자들을 하나도 나눌 수 없는 양의 정수
2. B가 가진 모든 숫자를 나눌 수 있고,  A가 가진 모든 숫자들을 하나도 나눌 수 없는 양의 정수

 

A가 가진 숫자 배열 arrayA, B가 가진 숫자 배열 arrayB가 주어질 때,
주어진 조건을 만족하는 가장 큰 양의 정수를 return 하는 solution을 완성해 주세요.

** 만약 조건을 만족하는 a가 없다면 0을 return 해주세요. **

 

첫 번째 예시를 예로 들면,

두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. => return 0

1. (X): A의 모든 숫자를 나눌 수 있는 숫자는 1이고, B의 모든 숫자는 1로 나눌 수 있기 때문

2. (X): B의 모든 숫자를 나눌 수 있는 숫자는 5이고, B의 숫자들 중 10일은 5로 나눠 떨어지기 때문

 

두 번째 예시를 예로 들면,

두 조건 중 하나를 만족하는 양의 정수는 10입니다. => return 10

1. (10) : A의 모든 숫자를 나눌 수 있는 숫자는 10이고, B의 숫자들은 모두 10으로 나눠 떨어지지 않기 때문

2. (X) : B의 모든 숫자를 나눌 수 있는 숫자는 1이고, B의 모든 숫자들은 모두 1로 나눠 떨어지기 때문

---

💡 아이디어

배열 A의 모든 숫자를 나눌 수 있는 숫자는 배열 A의 공약수라는 말과 같습니다.
그리고 조건 1, 2를 만족하는 가장 큰 수를 찾는 것이므로 최대 공약수를 찾아,
그 수가  B에서 나눠 떨어지는지 확인합니다.

 

📗 풀이 과정

1. 최대공약수를 구하는 방법은 유클리드 호제법을 사용했습니다.

유클리드 호제법은 최대공약수를 구하는 방식 중 하나입니다.

유클리드 호제법을 모르시는 분들은 아래 영상 참고하시면 도움이 될 것 같습니다!
https://www.youtube.com/watch?v=TxdljAFjTNw

유클리드 호제법을 이용해 반복문으로 최대공약수를 구하는 함수를 만들어줍니다.

//최대공약수 구하기
int gcd(int a, int b){
    if(a<b){
        int temp=a;
        a=b;
        b=temp;
    }
    while(b!=0){
        int temp=b;
        b=a%b;
        a=temp;
    }
    return a;
}

다른 방법으로 재귀를 사용해 만들 수도 있지만 a가 항상 b보다 커야 하는 조건을 따로 추가 야해야 하기 때문에 위의 방법을 사용했습니다.

 

2. 배열 A  모든 숫자의 최대공약수를 구합니다.

1번에서 구현한 최대공약수를 구하는 함수는 두 수의 최대공약수를 구하는 것으로,

 A 배열의 원소와 이전에 구했던 최대공약수와의 최대공약수를 구합니다.

//배열의 최대공약수 구하기
int arrayGCD(int[] arr){
    if(arr.length==1) return arr[0];
        
    int g=gcd(arr[0],arr[1]);
        
    for(int i=2;i<arr.length;i++){
        g=gcd(g,arr[i]);
    }
    return g;
}

 

3. 배열 A의 최대공약수가 배열 B의 모든 원소들을 나눌 수 없는지 확인하기 위한, 함수를 만들어줍니다.

//arr의 숫자 하나라도 d로 나눠지는지 확인
boolean canDivide(int d, int[] arr){
	for(int i=0;i<arr.length;i++){
	    if(arr[i]%d==0) return true;
	}
	return false;
}

단순하게 B배열을 돌면서 A의 최대공약수로 나눠 떨어지는 수가 있다면 true(나눠 떨어진다)를 return 해주고,

마지막까지 나눠 떨어지지 않았다면 false(나눠 떨어지지 않다)를 return 하는 함수입니다.

 

4. 위에서 만든 gcd, arrayGCD, canDivide 함수를 이용해,
조건 1, 2 중 하나를 만족하는 가장 큰 수를 구하는 함수 solution을 구현할 수 있습니다. 

아래의 전체 코드를 참고해 주세요.

---

전체 코드

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        
        //A가 가진 숫자들을 모두 나눌 수 있는 수
        int a=arrayGCD(arrayA);//arrayA의 최대공약수
        
        if(a!=1 && !canDivide(a,arrayB)) answer=a; // a로 B의 모든 숫자를 나눌 수 없는지 확인
        
        //B가 가진 숫자들을 모두 나눌 수 있는 수
        int b = arrayGCD(arrayB);//arrayB의 최대 공약수
        
        if(b!=1 && !canDivide(b,arrayA)) answer=Math.max(answer,b);
        
        return answer;
    }
    //배열의 최대공약수 구하기
    int arrayGCD(int[] arr){
        if(arr.length==1) return arr[0];
        
        int g=gcd(arr[0],arr[1]);
        
        for(int i=2;i<arr.length;i++){
            g=gcd(g,arr[i]);
        }
        return g;
    }
    //최대공약수 구하기
    int gcd(int a, int b){
        if(a<b){
            int temp=a;
            a=b;
            b=temp;
        }
        while(b!=0){
            int temp=b;
            b=a%b;
            a=temp;
        }
        return a;
    }
    //arr의 숫자 하나라도 d로 나눠지는지 확인
    boolean canDivide(int d, int[] arr){
        for(int i=0;i<arr.length;i++){
            if(arr[i]%d==0) return true;
        }
        return false;
    }
}