[JS] 프로그래머스 : 최대공약수와 최소공배수, 유클리드 호제법

 

 

📝 문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

🫠 나의 풀이

function solution(n, m) {
  const gcd = (a, b) => (a % b === 0 ? b : gcd(b, a % b));
  const lcm = (a, b) => (a * b) / gcd(a, b);

  return [gcd(n, m), lcm(n, m)];
}

 

유클리드 호제법

n > m 일 때,

n 을 m 으로 나눈 나머지를 r 이라 한다. gcd(n, m) = gcd(m, r) 과 같다.

r 이 0 이라면 그 때의 m 이 최대공약수다

n = 24, m = 16 이라면 gcd(24, 16) = gcd(16, 8) = gcd(8, 0)

gcd = 8

 

n < m 이라면, 처음에 m 을 n % m === n 으로 나눈다.

 

최대공배수는 두 수를 곱한 값을 최대공약수로 나눈 값과 같다.

 

🧞‍♂️ 다른  풀이

// 약수 구하기
function solution(n, m) {
  let gcd = 1;

  for (let i = 2; i <= Math.min(n, m); i++) { // n, m 중 작은 수를 골라 기준을 잡는다.
    if (n % i === 0 && m % 2 === 0) gcd = i;
    // i 를 하나씩 키우며 n, m 둘 다 나머지를 0으로 갖는 수가 나올 때 gcd 에 값을 넣는다.
  }

  return gcd;
}

 

// 최소공배수 구하기
function solution(n, m) {
  let lcm = 1;

  while (true) {
    if (lcm % n === 0 && lcm % m === 0) break;
    // lcm 을 하나씩 키우며 lcm 을 n, m 으로 나눴을 때 둘 다 나머지가 0이라면 반복문을 멈춘다.
    lcm++;
  }

  return lcm; // 최대공약수를 찾은 상태라면 n * m / gcd 를 해줘도 된다.
}

 

 

 

🔗 https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스