[Swift] 프로그래머스 LV. 2 N개의 최소공배수

프로그래머스 LV. 2 N개의 최소공배수 

 

 ✅ 최소공배수와 최대공약수를 사용할 때는 직접 구하지 말고 유클리드 호제법을 이용하자.

 

 

호제법을 이용한다면 쉽게 풀수가 있다.

struct p12953 {
    static func run() {
        print(p12953.solution([2,6,8,14])) // 168
    }
    
    static func solution(_ arr:[Int]) -> Int {
        // 최소공배수 찾는 알고리즘 하나 마련해서 쭉 돌자
        var prev = arr[0]
        for i in 1..<arr.count {
            prev = lcm(prev, arr[i])
        }
        
        return prev
    }
    
    // 최소공배수
    static func lcm(_ a: Int, _ b: Int) -> Int {
        return (a * b) / gcd(a, b)
    }
    
    // 최대공약수
    static func gcd(_ a: Int, _ b: Int) -> Int {
        var a = a
        var b = b
        var r = 0
        
        while b != 0 {
            r = a % b
            a = b
            b = r
        }
        
        return a
    }
}