[프로그래머스] 숫자 카드 나누기 Lv2

https://school.programmers.co.kr/learn/courses/30/lessons/135807?language=javascript

프로그래머스

 

const gcd = (a, b) => {
  if (b === 0) {
    return a;
  }
  return gcd(b, a % b);
}

function solution(arrayA, arrayB) {
  var answer = 0;
  let [gcdA, gcdB] = [arrayA[0], arrayB[0]];
  for (let i = 1; i < arrayA.length; i++) {
    gcdA = gcd(gcdA, arrayA[i]);
    gcdB = gcd(gcdB, arrayB[i]);
  }
  if (gcdA === 1) gcdA = 0;
  if (gcdB === 1) gcdB = 0;

  if (arrayA.every((v) => v % gcdB !== 0)) answer = Math.max(answer, gcdB);
  if (arrayB.every((v) => v % gcdA !== 0)) answer = Math.max(answer, gcdA);

  return answer;
}

 

해당 문제는 유클리드 호제법을 통해 최대공약수를 구하고 그 중 가장 큰 값을 구하는 문제이다.

 

유클리드 호제법(Euclidean algorithm)은 두 수의 최대공약수(GCD)를 구하는 알고리즘으로, 두 수 a와 b가 있을 때, a를 b로 나눈 나머지를 구하고, 그 나머지를 새로운 b로 설정하여 반복합니다. 이 과정에서 나머지가 0이 되면, 그때의 b 값이 두 수의 최대공약수가 됩니다.

유클리드 호제법 정의:

두 수 a와 b에 대해 최대공약수(GCD)를 구하는 알고리즘으로, 다음과 같은 원리를 사용합니다:

• a = b * q + r (q는 몫, r은 나머지)
• 그 후, a와 b를 각각 b와 r로 교체하고 반복합니다.
• r이 0이 되면 b가 최대공약수입니다.

 

1. 재귀 함수 방식으로 최대공약수 구하기

재귀 함수는 함수가 자기 자신을 호출하는 방식으로, 유클리드 호제법을 재귀적으로 구현할 수 있습니다. 이 방법은 간결하고 이해하기 쉽습니다.

 

// 유클리드 호제법을 이용한 최대공약수 구하기 (재귀 함수 방식)
function gcdRecursive(a, b) {
  // 기저 조건: b가 0이면 a가 최대공약수
  if (b === 0) {
    return a;
  }
  // 재귀 호출: b와 a % b의 최대공약수를 찾음
  return gcdRecursive(b, a % b);
}

// 사용 예시
let num1 = 56;
let num2 = 98;
let result = gcdRecursive(num1, num2);
console.log(`최대공약수 (재귀 방식): ${result}`);

 

2. 재귀 함수 방식이 아닌 (반복문 방식)으로 최대공약수 구하기

재귀 대신 반복문을 사용하여 같은 결과를 얻을 수 있습니다. 반복문 방식은 함수 호출 스택이 쌓이지 않아서 더 효율적일 수 있지만, 코드가 다소 길어질 수 있습니다.

 

// 유클리드 호제법을 이용한 최대공약수 구하기 (반복문 방식)
function gcdIterative(a, b) {
  while (b !== 0) {
    let temp = b;
    b = a % b;  // 나머지를 구함
    a = temp;   // a와 b를 교환
  }
  return a;  // b가 0이 되면 a가 최대공약수
}

// 사용 예시
let num1 = 56;
let num2 = 98;
let result = gcdIterative(num1, num2);
console.log(`최대공약수 (반복문 방식): ${result}`);

 

 

 

왜 최대공약수가 계속 업데이트되어도 괜찮을까?

1. 최대공약수(GCD)의 성질:
   • 두 수 a와 b에 대해 최대공약수는 그 둘을 나누는 가장 큰 수입니다. 예를 들어, gcd(12, 18)은 6입니다.
   • 세 개 이상의 수에 대해 최대공약수를 구할 때는, 그 수들의 순차적인 최대공약수를 구할 수 있습니다. 즉, gcd(a, b, c)는 gcd(gcd(a, b), c)로 구할 수 있습니다.
2. 업데이트 방식:
   • gcdA는 처음에 arrayA[0]로 설정됩니다. 그 후 arrayA[1], arrayA[2], ..., arrayA[n-1]에 대해 반복문을 돌며 최대공약수를 계산합니다.
   • gcdB도 마찬가지로 처음에 arrayB[0]으로 설정되고, arrayB[1], arrayB[2], ..., arrayB[n-1]에 대해 반복문을 돌며 최대공약수를 계산합니다.
   • 이 방식이 맞는 이유는, 최대공약수는 두 수의 공약수 중 가장 큰 값인데, 이를 세 개 이상의 수에 대해 확장할 때, 각 수의 최대공약수를 차례대로 구해가면 모든 수에 대한 최대공약수를 찾을 수 있기 때문입니다.
3. 결과적으로:
   • gcdA는 arrayA의 모든 원소들의 최대공약수로 끝나고, gcdB는 arrayB의 모든 원소들의 최대공약수로 끝납니다.
   • 이 두 값이 arrayA와 arrayB에서 각각 나누어 떨어지지 않는지 확인한 후 가장 큰 값을 구합니다.