최대공약수와 최대공배수

최대공약수와 최대공배수

2020.07.28

// 소인수분해를 할 것이기 때문에 소수를 판별하는 함수 필요
const isPrimeNumber = (num) => {
  if (num <= 1) {
    return false;
  }
  if (num <= 3) {
    return true;
  }
  if (num % 2 == 0 || num % 3 == 0) {
    return false;
  }
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) {
      return false;
    }
  }
  return true;
};

// 조건문 캡슐화를 위한 함수
const isZeroRemainder = (num, divisor) => {
  return !(num % divisor);
};

// 소인수 분해 결과를 hash에 담음
const initHash = (hash, divisor) => {
  if (!hash.hasOwnProperty(divisor)) {
    hash[divisor] = 1;
  } else {
    hash[divisor]++;
  }
  return hash;
};

// 재귀로 소인수분해 실행
const primeFactorization = (hash, divisor, num) => {
  if (isPrimeNumber(divisor) && isZeroRemainder(num, divisor)) {
    hash = initHash(hash, divisor);
    num /= divisor;
    if (num == 1) {
      return hash;
    }
    return primeFactorization(hash, divisor, num);
  }
  divisor++;
  return primeFactorization(hash, divisor, num);
};

// 두 수의 최대공약수 구하기
const getGCD = (firstHash, secondHash) => {
  let result = 1;
  for (const key in firstHash) {
    if (secondHash.hasOwnProperty(key)) {
      result *= key ** Math.min(firstHash[key], secondHash[key]);
    }
  }
  return result;
};

// 두 수의 최소공배수 구하기
const getLCM = (firstHash, secondHash) => {
  const keysOfFirst = Object.keys(firstHash);
  const keysOfSecond = Object.keys(secondHash);
  const setOfKeys = new Set([...keysOfFirst, ...keysOfSecond]);
  const arrOfKeys = Array.from(setOfKeys);
  return arrOfKeys.reduce((acc, key) => {
    if (firstHash[key] && secondHash[key]) {
      return (acc *= key ** Math.max(firstHash[key], secondHash[key]));
    }
    if (firstHash[key]) {
      return (acc *= key ** firstHash[key]);
    }
    if (secondHash[key]) {
      return (acc *= key ** secondHash[key]);
    }
  }, 1);
};

const solution = (n, m) => {
  const pfOfN = primeFactorization({}, 2, n);
  const pfOfM = primeFactorization({}, 2, m);
  const greatestCommonDivisor = getGCD(pfOfN, pfOfM);
  const lowestCommonMultiple = getLCM(pfOfN, pfOfM);
  return [greatestCommonDivisor, lowestCommonMultiple];
};

• getLCM 함수에서 reduce의 보조 함수를 밖으로 빼낼 수가 없다.
  (firstHash와 secondHash를 인자로 전달할 방법이...)

• 소인수분해가 정석일 거라 생각해서 이렇게 풀었는데 어째 코드가 너무 길고 복잡하다 했더니 아예 방향을 잘못 잡은 거였다.
  (reduce보조 함수 빼는 게 중요한 게 아니라고)

// 소인수분해를 할 것이기 때문에 소수를 판별하는 함수 필요
const isPrimeNumber = (num) => {
  if (num <= 1) {
    return false;
  }
  if (num <= 3) {
    return true;
  }
  if (num % 2 == 0 || num % 3 == 0) {
    return false;
  }
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) {
      return false;
    }
  }
  return true;
};

// 조건문 캡슐화를 위한 함수
const isZeroRemainder = (num, divisor) => {
  return !(num % divisor);
};

// 소인수 분해 결과를 hash에 담음
const initHash = (hash, divisor) => {
  if (!hash.hasOwnProperty(divisor)) {
    hash[divisor] = 1;
  } else {
    hash[divisor]++;
  }
  return hash;
};

// 재귀로 소인수분해 실행
const primeFactorization = (hash, divisor, num) => {
  if (isPrimeNumber(divisor) && isZeroRemainder(num, divisor)) {
    hash = initHash(hash, divisor);
    num /= divisor;
    if (num == 1) {
      return hash;
    }
    return primeFactorization(hash, divisor, num);
  }
  divisor++;
  return primeFactorization(hash, divisor, num);
};

// 두 수의 최대공약수 구하기
const getGCD = (firstHash, secondHash) => {
  let result = 1;
  for (const key in firstHash) {
    if (secondHash.hasOwnProperty(key)) {
      result *= key ** Math.min(firstHash[key], secondHash[key]);
    }
  }
  return result;
};

const solution = (n, m) => {
  const pfOfN = primeFactorization({}, 2, n);
  const pfOfM = primeFactorization({}, 2, m);
  const greatestCommonDivisor = getGCD(pfOfN, pfOfM);
  const lowestCommonMultiple = (n * m) / greatestCommonDivisor;
  return [greatestCommonDivisor, lowestCommonMultiple];
};

• 최소공배수를 최대공약수를 이용해서 구할 수 있다는 걸 왜 몰랐을까...
  (최소공배수 X 최대공약수 = a X b)

• 최소공배수 구하는 함수만 없애도 실행 시간이 거의 반으로 뚝떨어진다.

• 내가 실전에서 뽑아낼 수 있는 최선은 아마 이 수준이겠지만, 여전히 개선의 여지가 있다.

// 두 수의 최대공약수 구하기
const getGCD = (first, second) => {
  if (second) {
    const newFirst = second;
    const newSecond = first % second;
    return getGCD(newFirst, newSecond);
  }
  return first;
};

const solution = (n, m) => {
  const greatestCommonDivisor = getGCD(n, m);
  const lowestCommonMultiple = (n * m) / greatestCommonDivisor;
  return [greatestCommonDivisor, lowestCommonMultiple];
};

• 유클리드 호제법이라고 한다.
  (이런걸 어케 알아...)

• 임의의 두 자연수 a,b가 있다고 가정(a>b)

• a를 b로 나눈 나머지를 r이라고 하면, r이 0일때 b가 최대공배수

• r이 0이 아니면, a는 b로, b는 r로 대체하여 다시 실행