숫자 카드 나누기 (최대공약수)

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

프로그래머스

 

 

문제 풀이

최대 공약수를 구하면 쉽게 풀 수 있는 문제이다. 최대 공약수를 구하는 방법은 여러 가지가 있지만 유클리드 호제법으로 해결했다.

 

유클리드 호제법이란?

두 자연수 간의 최대공약수(GCD)를 빠르고 효율적으로 구하는 알고리즘

◆ 두 자연수 a와 b (단, a > b)가 주어졌을 때 최대공약수 GCD(a, b)를 구하는 과정은 다음과 같습니다

 

 1. a를 b로 나눈 나머지 r을 구합니다. (식: a = b × q + r)

 

 2.만약 r = 0이라면, 나누는 수인 b가 최대공약수입니다.

 

 3.r ≠ 0이라면, a에 b를 대입하고 b에 r을 대입한 후 1번 과정으로 되돌아가 반복합니다

 

즉, gcd(a, b) = gcd(b, r)

 

예시: gcd(48, 18) 구하기

48 = 18 × 2 + 12   →  gcd(48, 18) = gcd(18, 12)
18 = 12 × 1 + 6    →  gcd(18, 12) = gcd(12, 6)
12 = 6 × 2 + 0     →  나머지가 0! 

따라서 gcd(48, 18) = 6

 

 

유클리드 호제법 코드 구현

 

재귀 방식

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

 

반복문 방식

public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

 

작성한 코드

class Solution {
        public int solution(int[] arrayA, int[] arrayB) {

        int resultA = arrayA[0];
        int resultB = arrayB[0];

        for (int i = 0; i < arrayA.length ; i++) {
            resultA = gcd(resultA, arrayA[i]);
            resultB = gcd(resultB, arrayB[i]);
        }

        if (arrayCheck(resultA, arrayB)) resultA = 0;
        if (arrayCheck(resultB, arrayA)) resultB = 0;

        return Math.max(resultA, resultB);
    }

    public boolean arrayCheck(int comNum, int[] array) {

        for (int num : array) {
            if (num % comNum == 0)
                return true;
        }

        return false;
    }

    // 유클리드 호제법
    public int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}