[Algorithm] 최대공약수와 최소공배수 (유클리드 호제법 사용) - 프로그래머스

최대공약수와 최소공배수 (유클리드 호제법을 사용하여)

문제 설명

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

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n m return

3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1

위의 설명과 같습니다.

입출력 예 #2

자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

처음 풀이

const solution = (n, m) => {
  let answer = [];
  let a = n;
  let b = m;

  while (m != 0) {
    let r = n % m;
    n = m;
    m = r;
  }
  answer[0] = n;
  answer[1] = (a * b) / answer[0];

  return answer;
};

• 삼항연산자와 재귀를 사용해 푸는 것이 헷갈려 while문으로 유클리드 호제법을 구현하였다
• while 반복문에서 n과 m의 값을 직접 수정하기 때문에, 최소공배수(answer[1]) 을 도출하기 위해서는 a와 b로 처음에 값을 복사하는 과정이 필요하였다

삼항연산자/재귀 적용한 풀이

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

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

• 최대공약수(gcd)를 구하는 함수와 최소공배수(lcm)을 구하는 함수를 따로 정의해 return문 안에 바로 넣어준다
• 로직은 위의 while문 사용했을 경우와 똑같다
  • 하지만, n과 m을 나눈 나머지가 0이 아니라면 재귀적으로 다시 m을 n으로, 나머지(=n%m)를 m으로 넣어 gcd함수를 돌게 한다
• lcm을 구할 때 굳이 변수에 값을 복사할 필요없이, gcd(n,m)으로 해결하면 된다