[Algorithm] N개의 최소공배수 (유클리드 호제법)

🖥 문제

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

🤔 풀이 방법

1. arr[0]과 arr[1]의 최대공약수를 유클리드 호제법을 이용하여 구한다.
2. 1번에서 구한 최대공약수를 이용하여 최소공배수를 구한다.
3. 2번에서 구한 최소공배수를 이용하여 arr[2]와의 최대공약수를 유클리드 호제법을 이용하여 구한다.
4. 3번에서 구한 최대공약수를 이용하여 최소공배수를 구한다.
5. 3, 4번을 반복한다.

👩🏻‍💻 Swift Code

import Foundation

func solution(_ arr:[Int]) -> Int {
    var gcd = 0
    var lcm = 0

    for i in 0..<arr.count-1 {
        var num1 = 0
        var num2 = 0

        // gcd
        if i == 0 {
            num1 = max(arr[i], arr[i + 1])
            num2 = min(arr[i], arr[i + 1])
        } else {
            num1 = max(lcm, arr[i + 1])
            num2 = min(lcm, arr[i + 1])
        }

        var r = 0
        while num1 % num2 != 0 {
            r = num1 % num2
            num1 = num2
            num2 = r
        }
        gcd = num2

        // lcm
        if i == 0 {
            lcm = arr[i] * arr[i + 1] / gcd
        } else {
            lcm = lcm * arr[i + 1] / gcd
        }

    }

    return lcm
}

 

코딩테스트 연습 - N개의 최소공배수