Swift) 프로그래머스(Lv1) 최대공약수와 최대공배수 (유클리드 호제법)

programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

안녕하세요 후르륵짭짭 입니다.

진짜 간단한 문제인데, 유클리드 호제법 항상 생각이 안나서,,,

기록 할려고 했습니다.

저는 호제법이 생각이 안나서 ㅠㅠ

이 문제 그냥 중학교 때 최소 공배수 / 최대 공약수로 풀었습니다.

쉬운 문제도 항상 퀄리티 안 좋게 푸는거 같습니다 ㅠㅠㅠ 

 

** 유클리드 호제법 알고리즘 **

soyeon님 코드 입니다

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 tempN = n
  var tempM = m
  var divid = 2

  var 약수 = 1
    
    while divid <= tempN && divid <= tempM{
    
        if (tempN % divid == 0) && (tempM % divid == 0) {
            tempN = tempN / divid
            tempM = tempM / divid
            약수 *= divid
            divid = 2
            continue
        }
        
        divid += 1
        
    }
    
    return [약수, 약수 * tempN * tempM]
}