출처: 프로그래머스 코딩 테스트 연습

문제 설명

두 수의 최소공배수(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

내가 제출한 코드

//[n1.n2,n3] -> [n1과n2의 최소공배수, n3]
func solution(_ arr:[Int]) -> Int {
    var data: [Int] = arr
    
    while data.count > 1 {
        if data[0] < data[1] {
            data.swapAt(0,1)
        }
        var lcm = data[0] * data[1] / gcd(data[0],data[1])
        data.removeSubrange(0..<2)
        data.append(lcm)
    }
    
    return data[0]
}

func gcd(_ p: Int, _ q: Int) -> Int{
    if q == 0 {
        return p
    }
    return gcd(q,p%q)
}

결과

(코드의 원리 설명)

아래 글은 코드가 왜 최소공배수와 최대 공배수를 구할 수 있는지 설명하는 글이다. 이유가 궁금하지 않다면 단순히 코드만 보는 것을 추천한다.

이번 문제는 N 개의 수에서 최소공배수를 구해야 한다. 우선 일반적인 경우인 두 개의 수에서 최소 공배수를 구하는 방법을 생각해 보자. 소인수 분해를 사용하는 방법이 있지만 다른 방법은 수1 * 수2 / 최대공약수의 식을 이용하는 방법이다. 위 식의 증명방법을 보고 싶다면 최소공배수 구하는 방법을 검색하거나 또는 소인수 분해를 생각하면 확인할 수 있을 것이다.

우리는 이제 2개의 수에서 최소 공배수를 구하는 방법을 알았다.(그렇다고 가정하자ㅋ). 이를 N 개(3개)인 경우로 확장한다. [n1, n2, n3] 세 개의 수에서 최소공배수를 구하기 위해 우선 n1과 n2의 최소공배수를 구한다. 이를 lcm1이라고 하자. 이제 이 lcm1와 n3의 최소공배수를 lcm2라고 하자. lcm2는 세 개의 수의 최소 공배수가 된다.

위의 사실이 이해가 안 가거나 수학적으로 확인하고 싶다면 소인수 분해를 생각해 보자. 예를 들어 3,10,24의 수가 있다. 이들을 소인수 분해로 표현하면 3(3), 10(2*5), 24(2^3*3)으로 표현된다. 최소 공배수는 이 세 개의 수의 소인수들에서 가장 큰 지수를 가진 소인수들의 곱으로 구할 수 있다. 위 경우에서는 2^3 * 3 * 5 = 120이 된다. 이 결과를 보면 3개의 소인수들을 한 번에 곱하여 계산한 것을 확인할 수 있다.

그러나 2개의 수 3(3), 10(2*5)=>30을 먼저 계산하고 계산한 결과와 나머지 1개의 수인 30(2*3*5), 24(2^3*3)=>120와 계산해도 결과는 120으로 같기 때문에 우리는 N개의 수를 2개씩 분할하여 N 개의 최소 공배수를 얻을 수 있다는 최종 결론을 얻는다. 그리고 계산 순서도 관계가 없다는 사실을 알 수 있다.

되게 말이 길었다.. 짧게 표현하고 싶었으나 다른 풀이들을 찾아봐도 제출한 코드들이 최소공배수를 얻는 원리에 대해서 기술한 글이 없길래 혹시나 궁금한 사람을 위해 최대한 설명을 하였다.

코드 설명

최대 공약수를 구하는 메소드 gcd 는 유클리드 알고리즘을 사용한다.

다음으로 N 개의 최소공배수를 구하는 과정이다.

var data: [Int] = arr
    
    while data.count > 1 {
        if data[0] < data[1] {
            data.swapAt(0,1)
        }
        var lcm = data[0] * data[1] / gcd(data[0],data[1])
        data.removeSubrange(0..<2)
        data.append(lcm)
    }

로직은 간단하다. 입력으로 들어온 배열의 앞쪽의 2개의 원소의 최소공배수를 구한다. 두 원소의 최소공배수를 구하면 이를 배열의 제일 끝에 추가한다. 그리고 최소 공배수를 구하는 데 사용된 수는 제거한다. 이를 배열의 원소가 1개 남을 때까지 반복하면 N 개의 수에서 최소공배수를 구할 수 있다.

다른 접근법 (시간 초과)

해당 방법은 단순한 방법이다. 물론 단순하고, 효율성이 매우 떨어지지만 이런 방법이 있다 정도로 참고하면 좋다고 생각하여 기술한다. 해당 방법은 주어진 배열에서 가장 큰 수에서 시작하여 1씩 증가하여 최소 공배수를 확인하는 방법이다.

코드는 다음과 같다.

var num = arr.max()!
    while true{
        if arr.count == arr.filter{num % $0==0}.count {
            break
        }
        num += 1
    }

단순히 1씩 증가한 값이 입력으로 주어진 배열에서 모든 원소에 대해 나누어떨어지는 경우 그 수는 최소공배수가 된다. 그러나 해당 방법은 효율적이지 못하다. 이는 실행 결과를 통해 확인할 수 있다.