[Swift Algorithm] N개의 최소공배수 Programmers(Lv.2)

문제 설명

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

 

내 문제 풀이

import Foundation

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

func LCM(_ n:Int, _ m:Int) -> Int {
    var gcd = 0
    var a = 0
    
    if n > m {
        a = n }
    else {
        a = m }
    
    while a > 0 {
        if (n%a == 0 && m%a == 0) {
            gcd = a
            break
        }
        else {
            a -= 1
        }
    }

    return n*m/gcd
}

• 여러 수의 최소공배수를 구하기 위해 우선 두 수의 최소 공배수를 구하는 함수 LCM을 작성했다.
• LCM 함수는 두 수를 입력 받고, 먼저 최대공약수를 구해준다.
  while문을 사용하여 더 큰 수 a가 0이 될 때까지 1씩 빼주며
  n, m을 나눠보다가 두 수 모두 나눠지는 순간 while문을 종료한다.
  그리고 최대공약수를 이용해 최소공배수 구하는 공식을 사용하여 최소공배수를 반환한다.
• solution 함수에서는 reduce를 이용해 LCM 함수에 arr 배열의 모든 원소를 넣어주었다.
  처음에 0과 최소 공배수를 구하면 안되기 때문에 1로 초기값을 설정해주었다.

 

💡 피드백

• 코드가 간결하지 못한 것 같아 나중에 다시 수정해봐야겠다,,!

 

---

 

🖍 [ 추가 ] 1주일 후 다시 풀어보기

func solution(_ arr:[Int]) -> Int {
    func lcmSolution(_ n1:Int, _ n2:Int) -> Int {
        var gcd = n1
        while gcd > 0 {
            if (n1 % gcd == 0 && n2 % gcd == 0) { break }
            else { gcd -= 1 }
        }
        return n1 * n2 / gcd
    }
    
    return arr.sorted().reduce(1){ lcmSolution($0, $1) }
}

• 함수 안에 함수를 작성해주었다. 
• 기본적으로 최대공약수 구하는 로직은 첫 번째 풀이와 같고, 배열의 최소공배수 구하는 부분이 달라졌다.
• 배열을 정렬하여 굳이 큰 수 작은 수를 따질 필요가 없어졌고, reduce를 사용해 함수를 적용해주었다.

 

---

 

문제

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