[Swift - 프로그래머스] N개의 최소공배수 구하기

문제 해석

---

N개의 숫자를 담은 배열이 주어졌을 때 이 수들의 최소 공배수를 구하는 함수를 작성하는 문제였습니다.

배열의 수들은 100 이하인 자연수이고 배열의 길이는 1부터 15 이하라고 합니다. 

여러 수의 최대 공배수를 구하기 위해 먼저 두 수의 최대 공배수를 구하는 방법에 대해 알아봅시다.

두 수 a, b의 최소공배수는 두 수의 곱을 두 수의 최대 공약수로 나누어 주어서 구할 수 있다는군요.

두 수의 최대 공약수는 유클리드 호제법을 이용하여 쉽게 구할 수 있습니다. 

이를 이용하여 배열의 첫 번째 원소와 두 번째 원소의 최소 공배수를 구하고 구한 최소 공배수와 그다음 원소와의 최소공배수를 비교하여 전체 N개의 수의 최소 공배수를 구하는 방식으로 문제를 해결할 수 있습니다.

더 생각해보기

---

주어진 배열에서 100 이하의 자연수인 원소가 최대 15개 존재한다면, 최소 공배수가 가장 큰 값은 100이하의 가장 큰 소수 15개의 값의 곱이라고 생각할 수 있습니다. 그렇다면 그 수들은 [31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]가 될 것입니다. 이들의 곱은 3.5636434e+26으로 Int의 최댓값인 9.2233e+18을 훌쩍 뛰어넘습니다. 하지만 문제에서는 리턴 값을 Int형으로 정해주었기 때문에 이러한 예외상황은 제외하고 값을 구하라는 의미 같습니다. 만약 다른 문제에서 추가적인 조건이 있는 상황이면 자료형의 타입을 잘 판단하여 계산해보면 좋을 것 같습니다.

문제 풀이 & 코드

---

func solution(_ arr:[Int]) -> Int {
    // 유클리드 호제법을 통해 최대공약수를 구하는 함수
    func gcdOfTwoNumbers(_ a: Int, _ b: Int) -> Int {
        let r = a % b
        
        if r != 0 {
            return gcdOfTwoNumbers(b, r)
        } else {
            return b
        }
    }
    // 최소 공배수를 구하는 함수
    func lcmOfTwoNumbers(_ a: Int, _ b: Int) -> Int {
        return a * b / gcdOfTwoNumbers(a, b)
    }
    
    // 1과 자기자신의 최소 공배수는 자기 자신임으로 1로 초깃값을 설정하고
    // reduce로 값을 계산
    return arr.reduce(1){lcmOfTwoNumbers($0, $1)}
}

---

참고

• 나무 위키: 최소공배수, 최대공약수, 유클리드 호제법