[프로그래머스][LV.2][Swift] N개의 최소공배수 (유클리드 호제법)

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

문제 설명

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

제한 사항

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

입출력 예

문제 설명

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

 

---

문제 해석

단서

(1) 최소공배수는 두 수의 곱을 최대공약수로 나눠서 구할 수 있다.

(2) 여러 수의 최소공배수는 두 수로 짝지어서 최소공배수를 만들어서 소거시켜주면 된다.

알고리즘

(1) 반복문을 통해 배열에 들어있는 수를 최소공배수로 만들어서 하나씩 소거시킨다.

코드

func GCD(_ a: Int, _ b: Int) -> Int {
    return b == 0 ? a : GCD(b, a % b)
}

func LCM(_ a: Int, _ b: Int) -> Int {
    return a * b / GCD(a, b)
}

func solution(_ arr:[Int]) -> Int {
    var result = arr[0]
    for i in 1..<arr.count {
        result = LCM(result, arr[i])
    }
    return result
}

얼마전 유클리드호제법을 사용한 최대공약수(GCD)와 최소공배수(LCM)을 구하는 방법을 배워서 이 문제에 적용할 수 있었습니다.

solution() 함수는 for문을 이용해 배열의 요소들을 LCM()함수에 넣어 하나씩 소거시키는 방법을 사용했습니다.

LCM()의 시간복잡도는 O(log n)이고 solution()의 for문의 시간복잡도는 O(n)이기 때문에 전체 시간복잡도는 O(n log n)입니다.

정답을 제출하고 다른 사람들의 풀이를 봤는데 reduce()를 사용해 for문을 멋지게 줄인 코드를 봐서 첨부합니다.

func GCD(_ a: Int, _ b: Int) -> Int {
    return b == 0 ? a : GCD(b, a % b)
}

func LCM(_ a: Int, _ b: Int) -> Int {
    return a * b / GCD(a, b)
}

func solution(_ arr:[Int]) -> Int {
    return arr.reduce(1) {LCM($0, $1)}
}