HackerRank - Between Two Sets

문제는 영어로 되어 있는데 내맘대로 해석을 했다. 

원문은 [여기] 참조하면 된다.

문제

a라는 배열의 최소공배수를 가지고 b라는 배열의 최소값에 이르기 까지 총 개수가 몇개인지 구하시오.

예를 들어서 a = [2, 4] 이고 b = [8, 16, 24] 이면 값은 2가 되는데 a 배열의 최소공배수는 4이고 b의 최소값이 8까지는 4, 8 이기 때문에 총 값이 2이다.

풀이

 
// getTotalX( [2,4], [8, 16, 24] ); 이렇게 동작시키는 함수
const getTotalX =(a, b) => calculateCommonDenominator(LCM(a), b);
 
// a의 최소공배수(lcm)를 가지고 arr의 최소값까지의 갯수를 구한다.
const calculateCommonDenominator = (lcm, arr, cnt = 0, temp = lcm) => {
    const minEl = Math.min(...arr);
    for(;temp <= minEl; temp += lcm) arr.every(o=>o%temp === 0) && cnt++;
    return cnt;
}
 
// 숫자 배열의 최소 공배수를 구한다.
const LCM = arr => arr.reduce( (p,a)=> p*a/MCD(p,a) );
 
// 두수의 최대공약수를 구한다.
const MCD = (a1, a2) => {
    let [less,greater] = a1 < a2 ? [a1, a2] : [a2, a1], temp = greater % less;
    while(temp) [temp, less] = [less % temp, temp];
    return less;
}
 

ES6를 사용해서 간략하게 보일수 있도록 짜보았다.

calculateCommonDenominator의 인자인 cnt와 temp은 원래는 변수 선언인데, 그렇게 하면 함수가 괜히 커지니까 파라미터 단에서 그냥 선언시켜 버렸다.

순서를 보면 이러하다.

1. 두 숫자의 최대 공약수를 구한다음에 그것을 이용해서 두 숫자의 최소공배수를 구한다.

2. 그렇게 a 배열의 모든 값들을 순회하면서 a 배열의 최소공배수를 구한다.

3. 그 최소공배수를 calculateCommonDenominator에 b배열과 같이 넣어준다.

4. b배열의 최소값을 찾은뒤에 반복문을 돌면서 b배열의 각 b숫자 값이 a값의 최소공배수의 배수에 대해서 배수인지를 체크한다.

5. 체크가 맞으면 카운트 한다.

6. b 배열의 최소값과 같거나 그보다 커지면 종료하고 카운트 한것을 반환한다.