[135807] 숫자 카드 나누기

✔ 숫자 카드 나누기

[프로그래머스 135807]

문제 분석하기

arrayA와 arrayB의 최대공약수를 찾은 후, 두 공약수가 서로의 배열을 나눌 수 없는지 확인하도록 함

이때 나눌 수 없다면 그 값의 최대값을 a로 갱신

손으로 풀어보기

1. arrayA와 arrayB의 최대공약수 찾기
2. 두 공약수가 서로의 배열을 나눌 수 없는지 확인
   • 이때 나눌 수 없다면 그 값의 최대값을 answer로 갱신
3. answer를 반환

슈도코드 작성하기

arrayA(철수가 가진 카드에 적힌 숫자들)
arrayB(영희가 가진 카드에 적힌 숫자들)
answer(주어진 조건을 만족하는 가장 큰 양의 정수)
gcdA(arrayA의 최대공약수) 구하기
gcdB(arrayB의 최대공약수) 구하기
if(카드들에 적힌 모든 숫자를 나눌 수 없는지(arrayB, gcdA))
    answer = Math.max(answer, gcdA)
if(카드들에 적힌 모든 숫자를 나눌 수 없는지(arrayA, gcdB))
    answer = Math.max(answer, gcdB)
answer 반환

최대 공약수 함수 {
    if(b가 0이라면)
        a가 최대 공약수
    else
        최대 공약수 함수(작은 수, 큰 수 % 작은 수)
}

카드들에 적힌 모든 숫자를 나눌 수 없는지 함수 {
    for(int a : array) 
        if(a를 gcd로 나눈 나머지가 0이라면)
            false 반환
    true 반환
}

코드 구현하기

/**
 * 135807) 숫자_카드_나누기
 */
public class L084_135807 {
    // arrayA(철수가 가진 카드에 적힌 숫자들)
    // arrayB(영희가 가진 카드에 적힌 숫자들)
    public int solution(int[] arrayA, int[] arrayB) {
        // answer(주어진 조건을 만족하는 가장 큰 양의 정수)
        int answer = 0;
        // gcdA(arrayA의 최대공약수) 구하기
        int gcdA = arrayA[0];
        // gcdB(arrayB의 최대공약수) 구하기
        int gcdB = arrayB[0];
        for (int i = 1; i < arrayA.length; i++) {
            gcdA = gcd(gcdA, arrayA[i]);
            gcdB = gcd(gcdB, arrayB[i]);
        }
        // arrayB 카드들에 적힌 모든 숫자를 gcdA로 나눌 수 없다면 조건을 만족하므로
        if (isNotDivisible(arrayB, gcdA))
            // answer을 갱신
            answer = Math.max(answer, gcdA);
        // arrayA 카드들에 적힌 모든 숫자를 gcdB로 나눌 수 없다면 조건을 만족하므로
        if (isNotDivisible(arrayA, gcdB))
            // answer을 갱신
            answer = Math.max(answer, gcdB);
        // answer 반환
        return answer;
    }

    // 최대 공약수 함수
    private int gcd(int a, int b) {
        // b가 0이라면
        if (b == 0)
            // a가 최대 공약수
            return a;
        else
            // 최대 공약수 함수(작은 수, 큰 수 % 작은 수)
            return gcd(b, a % b);
    }

    // 카드들에 적힌 모든 숫자를 나눌 수 없는지 함수
    private boolean isNotDivisible(int[] array, int gcd) {
        for (int a : array)
            // a를 gcd로 나눈 나머지가 0이라면
            if (a % gcd == 0)
                // false 반환
                return false;
        // true 반환
        return true;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L084_135807 solution = new L084_135807();

        int[] arrayA = { 10, 20 };
        int[] arrayB = { 5, 17 };

        int result = solution.solution(arrayA, arrayB);

        System.out.println(result);
    }
}