[Programmers] 숫자 카드 나누기 -Javascript

INDEX

 

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

프로그래머스

 

 

Solution

어느 한쪽의 모든 숫자 카드를 나눌 수 있는 a라는 숫자는 공약수 일 것입니다.

가장 큰 a를 뽑아야 하니 최대 공약수를 뽑아야 되는 문제입니다.

 

만약 [4, 6, 12] 가 있을 때 이 숫자들의 최대공약수를 구하는 방법은 단순하게 풀면 가장 작은 숫자 4부터 2까지 반복문을 통해 모든 숫자가 그 숫자로 나눠지는지 확인하면 됩니다.

 

하지만 조건을 살펴보면 배열의 원소 개수가 1억 개까지 나올 수 있습니다. 절대 Brute force 방식으로는 풀 수 없습니다.

 

최대 공약수를 산출할 수 있는 알고리즘에는 유클리드 호제법 이 있습니다. 

개념은 너무 단순합니다.

유클리드 호제법
a 와 b 가 있을 때(a> b) a를 b로 나눈 나머지가 0 이면 이 둘의 최대 공약수는 b입니다.
하지만 나눠지지 않는다면 b를 r로 나눈 값이 0이 될 때 r 이 이들의 최대 공약수입니다. 

코드로 구현해 보면 아래와 같습니다.

function gcd(a,b){
    let mod = a % b;
    while(mod > 0){
        a = b;
        b = mod;
        mod = a % b;
    }
    return b;
}

 

주어지는 배열은 두 개가 아닌 1억 개까지 가능합니다. 이 들의 최대 공약수를 구하기 위해선

array [0]과 array [1]의 최대공약수 R을 구한 뒤 R과 array [2]의 최대공약수 R'을 구하고 R'과 array [3]의 최대공약수를 구하는 방법으로 진행합니다.

 

function getGcdOfArray(array){
    let gcd_ = gcd(array[0], array[1]);
    for(let i=2; i< array.length; i++){
        gcd_ = array[i] > gcd_ ? gcd(array[i], gcd_) : gcd(gcd_, array[i])
        if(gcd_ === 1) { //공약수가 없다면
            return 0;
        }
    }
    return gcd_;
}

 

사전 작업은 마쳤습니다. 이제 solution 함수를 짜보죠.

function solution(arrayA, arrayB) {
    arrayA = arrayA.sort((a,b)=> b-a); //유클리드 호제법을 사용하기 위해선 큰 수가 먼저 나와야 한다.
    arrayB = arrayB.sort((a,b)=> b-a);
    const aGcd = arrayA.length>1 ? getGcdOfArray(arrayA) : arrayA[0]; //원소의 개수가 하나면 그 수가 최대공약수가 된다.
    const bGcd = arrayB.length>1 ? getGcdOfArray(arrayB) : arrayB[0]; //각 최대공약수를 구한다.
    
    let isAGcdOk, isBGcdOk;
    if(aGcd > 0){ A배열에 1이 아닌 최대공약수가 존재한다면 
        isAGcdOk= true;
        for(let i=0; i< arrayB.length; i++){
            if(arrayB[i] % aGcd === 0) {
                isAGcdOk = false;
                break;
            }
        }
    }else isAGcdOk = false;
    
    if(bGcd > 0){ B배열에 1이 아닌 최대공약수가 존재한다면 
        isBGcdOk = true;
        for(let i=0; i< arrayA.length; i++){
            if(arrayA[i] % bGcd === 0) {
                isBGcdOk = false;
                break;
            }
        }
    }else isBGcdOk = false;
    
    
    if(!isBGcdOk && !isAGcdOk) return 0;
    else if(!isBGcdOk && isAGcdOk) return aGcd;
    else if(!isAGcdOk && isBGcdOk) return bGcd;
    else return Math.max(aGcd, bGcd);
}

각 배열의 최대 공약수를 구했더라도 문제에서 나온 조건에 맞아야 합니다. 다른 배열의 원소들이 한 배열의 최대공약수로 나눠지면 안 됩니다. 이 조건을 구현하기 위해 isAGcdOk와 isBGcdOk라는 변수를 활용했습니다. 변수 이름을 보면 딱 알 수 있습니다. 이게 true 면 arrayA의 최대공약수가 조건을 만족시킨 거구나 알 수 있죠.

이처럼 저는 코딩테스트 문제를 풀 때도 변수의 이름을 좀 신경 쓰는 편입니다. 그래야 저도 헷갈리지 않고 문제를 풀 수가 있더라고요.