프로그래머스 - L1 최대공약수와 최소공배수

설계

수학적 공식과 동일하게 접근

git : 최대공약수와 최소공배수

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12940

---

문제 풀이

∙ getGCD : 최대공약수 구현

두 수 중 작은 수를 선택해 역순으로 for문을 돌아 둘 다 나눠지는 값이 최대공약수

∙ getLCM : 최소공배수 구현

n은 m 만큼 반복을 통해 배수를 Set에 담기

m은 n 만큼 반복을 통해 배수를 Set에 담기

두 Set의 교집합을 구하여 min 값을 반환하면 최소 공배수

func solution(_ n:Int, _ m:Int) -> [Int] {
    var result: [Int] = []
    
    result.append(getGCD(n,m))
    result.append(getLCM(n,m))
    
    
    return result
}

func getGCD(_ n: Int, _ m: Int) -> Int {
    var result: Int = 0
    
    for i in stride(from: min(m, n), through: 1, by: -1) {
        
        if(n % i == 0 && m % i == 0) {
            result = i
            break
        }
    }

    return result
}

func getLCM(_ n: Int, _ m: Int) -> Int {
    var result: Int = 0
   
    var nSet: Set<Int> = []
    var mSet: Set<Int> = []
    
    for i in 1...m {
        nSet.insert(n * i)
    }
    
    for i in 1...n {
        mSet.insert(m * i)
    }
    
    result = nSet.intersection(mSet).min()!
    return result
}

다른 사람 풀이 분석

프로그래머스 - soyeon , parkchanwoong , fc750r , 천수빈 외 6 명

func gcd(_ a: Int, _ b: Int) -> Int {
    let mod: Int = a % b
    return 0 == mod ? min(a, b) : gcd(b, mod)
}

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

func solution(_ n:Int, _ m:Int) -> [Int] {
    return [gcd(n, m), lcm(n, m)]
}

∙ 최소공배수 = 두수의 곱 / 최대공약수

∙ 최대공약수 방식은 재귀로 구현 수학적 지식이 필요한거 같습니다 ….

프로그래머스 - 익명

func solution(_ n:Int, _ m:Int) -> [Int] {
    var first: [Int] = []
    for index in 1...n {
        if n % index == 0  && m % index == 0 {
            first.append(index)
        }
    }
    let maxValue: Int = first[first.count-1]
    return [maxValue ,(n * m)/maxValue ]
}

∙ 최소공배수 = 두수의 곱 / 최대공약수

∙ 최대공약수는 반복문을 통해 구현

정리

∙ 최소공배수 = 두수의 곱 / 최대공약수 활용하면 간단히 구현이 가능 할 것 같습니다.

∙ 너무 비효율적으로 하지 않는다는 기준으로 자신 있는 방식으로 구현하면 되지 않을까?!?

---