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

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

프로그래머스

 

접근 방법

1. 두 배열 A, B에서 다음 두 조건 중 하나를 만족하는 최대 양의 정수 a를 찾아야한다
   1. A의 모든 원소와 나누어 떨어지고, B의 모든 원소와 나누어 떨어지지 않는다
   2. B의 모든 원소와 나누어 떨어지고, A의 모든 원소와 나누어 떨어지지 않는다.
2. 즉, A의 최대공약수가 B의 모든 원소와 나누어 떨어지지 않는다 -> 답 후보
3. B의 최대공약수가 A의 모든 원소와 나누어 떨어지지 않는다 -> 답 후보
4. 둘 다 참이면, 둘 중 최대값
5. 둘 중 하나가 참이면 해당 값
6. 둘 다 아니면 0 반환

 

(참고) 최대 공약수 최소 공배수

최대 공약수(GCD, 유클리드 호제법)

int gcd(int a,int b){
    if(a == 0) return b;
    return gcd(b%a, a);
}

두 수 A,B에 대해 A를 B로 나눈 나머지를 r이라고 하면 GCD(A,B) = GCD(B,r)이다.

ex) GCD(20,12) = GCD(12,8) = GCD(8,4) =GCD(4,0) = 4

최소 공배수 (LCM)

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

A * B = GCD(A,B) * LCM(A,B)

 

코드

import java.util.*;
class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int a = getGcd(arrayA);
        int b = getGcd(arrayB);
        
        boolean flagA = a != 1 && canNotAllElementDivide(a, arrayB);
        boolean flagB = b != 1 && canNotAllElementDivide(b, arrayA);
        
        int answer = 0;
        if(flagA && flagB)answer = Math.max(a,b);
        else if(flagA) answer = a;
        else if(flagB)answer = b;
        
        return answer;
    }
    int getGcd(int[] arr){
        int res = arr[0];
        for(int i = 1; i < arr.length ; i++){
            res = gcd(res, arr[i]);
            if(res == 1) break;
        }
        return res;
    }
    int gcd(int a,int b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    boolean canNotAllElementDivide(int num, int[] arr){ 
        // 모든 원소가 num으로 나누어 떨어지지 않는다
        return Arrays.stream(arr).allMatch(i -> i% num != 0);
    }
}