N개의 최소 공배수 문제 바보같이 풀기

나는 알고리즘 공부를 하기 위해 프로그래머스에 들어간다. 오랜만의 알고리즘이기 때문에 lv3보다는 만만해보이는 lv2로 예열을 시키기로 했다. 그렇게 만난 다음의 문제.

Lv.2에 정답률이 꽤나 높은 문제에 속한다. 문제는 다음과 같다.

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

해당 문제를 보고 일단 최소 공배수를 구하는 함수를 만드는 것이 중요하다고 판단하여, 알고리즘을 파악하기 시작했다. 일단 내 머리로 최소 공배수를 구하는 과정을 곰곰히 생각해봤다. 그랬더니 난 최소 공배수를 이렇게 구하더라.

내 머리로 최소 공배수 구하기

6과 8의 최소공배수를 구하는 상황이라고 가정하자.

내 머릿속:
둘의 공배수를 구하기 위해 각각의 수를 1 곱해보고, 2곱해보고, 3곱해보고 , ... 하더라. 이걸 직접 하나하나 다 해본다면?

6x1 != 8x1
6x2 != 8x1
6x2 != 8x2
6x3 != 8x2
6x3 != 8x3
6x4 == 8x3

여기서 어떤 경우에 곱하는 수에 1을 더하는지 확인해 봤더니? 더 낮은 수의 곱하는 수에 1을 더하더라.

6x1 < 8x1
6x2 > 8x1
6x2 > 8x2
6x3 < 8x2
6x3 < 8x3
6x4 = 8x3

이렇게 최소 공배수를 구하는 알고리즘을 파악하고 이제 어떻게 구현을 할지 스케치를 했다.

solution() 함수에는 다음이 들어가요
- arr의 길이가 1일때 까지 반복
- 리턴값 = 함수(arr[0], arr[1])
- arr.splice(0, 2)
- arr.push(리턴값)

lcm() 함수에는 다음이 들어가요
- a와 b를 받음
- a와 b가 같을 때 까지 반복
- a와 b중 작은 쪽에 기존 값에서 1씩 곱해나감

최소 공배수 구하는 함수

내가 스케치한 것을 기반으로 lcm함수를 다음과 같이 구현했다.

const calcLCM = (paramA, paramB) => { //a와 b를 받음
    let a = paramA, b = paramB;
    let countA = 1, countB = 1;
    
    while(true) {
        if(a===b) return a; //a와 b가 같을 때 까지 반복
        
        // a와 b중 작은 쪽에 기존 값에서 1씩 곱해나감
        if(a>b) {
            countB++;
            b = paramB * countB;
        } else {
            countA++;
            a = paramA * countA;
        }
    }
}

전체 코드

최종적으로 다음과 같은 코드를 구현하였다. reduce함수를 사용해도 되었지만, 함수에 도움을 최대한 받지 않고 하기 위해 while문을 사용하였다.

function solution(arr) {
    while(arr.length > 1) {
        const lcm = calcLCM(arr[0], arr[1]);
        arr.splice(0, 2);
        arr.push(lcm);
    }
    
    return arr[0];
}

const calcLCM = (paramA, paramB) => {
    let a = paramA, b = paramB;
    let countA = 1, countB = 1;
    
    while(true) {
        if(a===b) return a;
        
        if(a>b) {
            countB++;
            b = paramB * countB;
        } else {
            countA++;
            a = paramA * countA;
        }
    }
}

다른사람 코드는?

결과에 통과하였다고 넘어갈 것이 아니라 다른 사람의 코드를 보며, 시야를 넓히는 것도 중요하다. 그래서 나는 다른 사람의 코드를 구경하기 시작했다. 이 글을 쓰게된 이유가 이제부터 나오기 시작한다.

이게 무슨? 다른 사람은 무슨 코드 한 줄로 끝난다.

function nlcm(num) {
 return num.reduce((a,b) => a*b / gcd(a,b))  
}

function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}

도대체 이게 뭔가 찾아봤더니, 최소 공배수를 구하는 방법 같은게 있더라...

최대 공배수 = 두 수의 곱 / 두 수의 최대 공약수

이러면 최대 공약수를 구해야 하는데 최대 공약수는 유클리드 호제법을 사용해서 구할 수 있다.

유클리드 호제법

2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘

유클리드 호제법 예시

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.

위의 방법론을 구현하면 gdc(a, b) 함수가 되는 것이다.

function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}

결론

유클리드 호제법으로 두 수의 최대 공약수를 구하고 두 수의 곱에 최대 공약수로 나누면 최대 공배수를 구할 수 있다.

최대 공배수 = 두 수의 곱 / 두 수의 최대 공약수

내 코드와 비교했을 때, 두 수의 크기가 커져도 성능적으로 유리한게 큰 장점이다. 그래서 이런 방법론을 적용한 알고리즘 코드를 사용하면 좋을 것 같다..!

그래도 수학 공식은 반칙이지.