프로그래머스 | 최대 공약수

📌 문제

배열 a에 n개의 정수가 들어있을 때, 내부의 정수들을 모두 아우르는 최대 공약수를 출력하세요.
예시 ) a = [6, 12, 5]; 최대 공약수 -> 2

✨ 해결 방법

최대 공약수는 다양한 방법으로 구할 수 있지만, 공통된 사항이 있습니다. 바로 1보다 크다는 것과, 가장 작은 수보다 더 클 수 없다는 것입니다.
따라서 코드를 효율적으로 구현하기 위해서는 모든 수를 순회하는 게 아닌, 범위를 배열의 가장 작은 수보다 작거나 같게 한정합니다.

다음으로, for문을 통해 각 정수가 i로 나누어지는지 검사합니다. 모두 나누어진다면 그 수는 정수들의 약수일 것이고, 그 약수를 계속 업데이트하면서 가장 큰 수를 구하면 됩니다.

💻 solution 1

function solution(a) {
    // 주어진 배열에서 최소값 찾기
    let gcd = 1;
    let minVal = Math.min(...a);

    // 최소값까지의 모든 수에 대해 최대공약수 계산
    for (let i = 2; i <= minVal; i++) {
        let isCommonFactor = true;

        for (let num of a) {
            if (num % i !== 0) {
                isCommonFactor = false;
                break;
            }
        }

        if (isCommonFactor) {
            gcd = i;
        }
    }

    return gcd;
}

우선 최대 공약수를 gcd로 선언한 후 1로 지정해놓습니다.
배열의 최소값은 Math.min(...arr) 사용하여 구합니다.
i가 1보다 크고, 최소값 이하일 때 for문을 반복합니다.
boolean을 이용하여 초기값을 true로 놓고, 배열 a의 각 정수를 순회하면서 i가 약수인지 구하고, 약수가 아니라면 false를 반환하고 for문을 멈춥니다. 만약 정수들의 공약수라면, 해당 i값을 gcd에 업데이트 합니다.

💻 solution 2

function gcd(x, y) {
    while (y !== 0) {
        const temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

function solution(a) {
    let resultGCD = a[0];

    for (let i = 1; i < a.length; i++) {
        resultGCD = gcd(resultGCD, a[i]);

        // 최대공약수가 1이면 더 이상 계산할 필요 없음
        if (resultGCD === 1) {
            break;
        }
    }

    return resultGCD;
}

solution 1은 해석하기 쉽지만 2중 for문을 사용하고 있습니다. 따라서 하나의 for 루프와 함수로 분리해보겠습니다.

gcd 함수는 유클리트 호제법을 이용하여 최대 공약수를 계산합니다. 두 수 x와 y에 대하여, x % y = r이라면, x와 y의 최대 공약수는 y와 r의 최대공약수와 같으며, 이 과정을 나머지가 0이 될때까지 반복합니다.

solution 함수에서는 배열 a의 각 원소에 대한 초대 공약수를 구합니다. 여기서 최대공약수가 1이 되면 나머지 원소들에 대한 계산이 무의미하므로 반복을 중단합니다.