[프로그래머스/JavaScript] Lv.2 숫자 카드 나누기

 

 

해당 문제는 최대 공약수를 구해 비교하는 문제이다.

 

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

 

 

 

---

1. 유클리드 알고리즘(유클리드 호제법)

유클리드 호제법은 두 자연수 사이의 최대공약수를 구하는 알고리즘이다.

* 정의
어떤 자연수 a, b가 있을 때 (a > b), 두 수의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.

1) 두 수 중에서 큰 수를 작은 수로 나눈다.
2) 만약 나누고 난 나머지가 0이라면 작은 수가 최대공약수이다.
3) 만약 나머지가 0 이 아니라면, 작은 수를 다시 나머지로 나눈다.
4) 이를 반복해서 나머지가 0 이 될 때, 그 수가 바로 두 수의 최대공약수이다.

 

 

---

2. 문제 풀이

// arrayA = 철수, arrayB = 영희
function solution(arrayA, arrayB) {
    // 1) 철수만 모든 숫자를 나눌수 있는 경우 
    let a = getDvsr(arrayA, arrayB);

    // 2) 영희만 모든 숫자를 나눌수 있는 경우 
    let b = getDvsr(arrayB, arrayA);
        
    return Math.max(a,b);
}
function getDvsr(arrayA, arrayB){
    let answer = 0;

    // 3) 최대 공약수를 구하는 재귀 함수
    const gcd =  (a, b) => a % b === 0 ? b : gcd(b, a % b);
    
    // 4) arrayA 배열에 담긴 값의 초대 공약수 구한다.
    arrayA.forEach(val => answer = gcd(answer, val));

    // 5) arrayB 배열의 값이 하나라도 arrayA의 최대 공약수로 나누어 진다면 0을 return 한다.
    if(arrayB.some(val => val%answer === 0)) return 0;
    
    // 6) 나누어지지 않으면 최대 공약수 return
    return answer;
}

• 유클리드 호제법의로 최대 공약수를 구한다.
• 고차함수 some()를 사용하여 하나라도 true면 0을 return 하게 한다.