[프로그래머스 | JavaScript] 최대공약수와 최소공배수 간결 풀이

<문제 설명>

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

 

<문제 풀이>

function solution(n, m) {
    let arrN = [] //n의 약수
    let arrM = [] //m의 약수
    let answer = []
    for(let i = 1; i <= n; i++){
        if(n%i===0){
            arrN.push(i)
        }
    }
    for(let i = 1; i <= m; i++){
        if(m%i ===0){
            arrM.push(i)
        }
    }
    let answer1 = (arrN.filter((a)=>arrM.includes(a)))
    answer.push(answer1[answer1.length-1]) // 최대공약수
answer.push(n*m/answer[0])//최소공배수
    
    return answer
}

최대공약수 = 두 수의 공통된 약수 중 가장 큰 수

최소공배수 = 두 수의 공통된 배수 중 가장 작은 수

 

사실 내 코드는 위 내용 그대로 한 것이라서 설명할게 없고,

내가 이 코드를 정확히 이해하기 위해서

정답과도 같은.. 정확하고 간결하게 정리된 코드를 설명하려 한다. 

function getLCM(num1, num2) {
  // 최대공약수 구하기
  function getGCD(a, b) {
    while (b !== 0) {
      let r = a % b;
      a = b;
      b = r;
    }
    return a;
  }
  // 최소공배수 구하기
  let gcd = getGCD(num1, num2);
  return (num1 * num2) / gcd;
}

먼저 최대공약수는 '유클리드 호제법'을 사용한다. 

유클리드 호제법(Euclidean algorithm)은 두 수의 최대공약수(GCD: Greatest Common Divisor)를 구하는 알고리즘으로, 유클리드(Euclid)가 발견하였다. 두 수를 나눈 나머지를 구하고, 그 나머지를 이전에 나눈 수로 나누는 과정을 반복하여 나머지가 0이 될 때까지 계산한다.

이때 마지막으로 나눈 수가 두 수의 최대공약수가 된다.

 

예를 들면, 두 수 18과 12의 최대공약수를 구하는 경우

18 ÷ 12 = 1 ... 6
12 ÷ 6 = 2 ... 0
따라서 18과 12의 최대공약수는 6 이다.

두 수 54와 24의 최대공약수를 구하는 경우

54 ÷ 24 = 2 ... 6
24 ÷ 6 = 4 ... 0
따라서 54와 24의 최대공약수는 6이다.

 

이제 이 공식을 코드로 구현하면, 나머지가 0이 될 때까지 계속 나누기 때문에 

a % b는 고정적으로 반복되면서, 조건을 맞추는 것이다. 

 

예시를 그대로 넣어보자. 

먼저 let r 은 a % b 즉, 18에서 12를 나누고 나머지인 6이다. 

나머지가 0이 될 때까지 a % b를 반복하기 때문에, 

a % b는 곧 기존에 나눈 값인 12와 6을 넣어주는 것이라서 식으로 치환하면

a = b, b = r 이 된다. 

18 % 12 = 1...6 이면, a = 18, b = 12, r = 6이다. 

그리고 나눈 값에서 나머지를 나누고 나머지를 구하는 작업을 반복한다. 

12 % 6인데, 변수로 생각하면 b % r 이 된다. b가 0이 아니면 계속 이것을 반복한다.

이 뜻은 반대로 b가 0이 되면 반복을 멈추게 된다. 

 

그렇게 최대공약수를 구하게 되면, 최소공배수는 간단하다. 

공통된 배수 중 가장 작은 수인데, 두 수를 곱하고 구한 최대공약수로 나누면 된다. 

 

<코멘트>

솔직히 최대공약수까지는 괜찮은데 최소공배수는 직접 계산하면 편하지만,

로직을 생각하라고 하면 아직 머리가 아프다. 방금 위에서 보았듯, 최소공배수가 오히려 간단하게 정리되지만 내가 푼 풀이를 보면 알 수 있듯이 최대공약수는 그냥 1차원적으로 풀 수 있는데,

최소공배수는 1차원적으로 풀게 되면 계속 곱하다가 겹치는 수를 찾기 때문에 비효율적이다. 

 

유클리드호제법이 간단하지만 내가 두려워하는 것은 아직 내가 while에 익숙하지가 않다. 

while 이 어렵다기 보다는, 반복문이고 조건이 명확하게 정해지면 break하거나 하는 것은 알지만,

그냥 그 문법 구조가 아직 어색한 것 같다. 다음에 최대공약수, 최소공배수 문제가 나오면

시도해보고 싶다.