프로그래머스 - 최대공약수와 최소공배수 [Swift]

최대공약수와 최소공배수 구하는 법은 자주 보는데도 잘 외워지질 않는다.

최대공약수는 a와 b라는 숫자에 대해 a를 b로 나눈 나머지를 r이라고 할 때,

gcd(a,b) -> gcd(b, r) -> ... 을 계속 반복하여 결국엔 처음 앞의 parameter가 0이 될 때까지 반복하면 된다.

최소공배수는 a와 b를 곱한 다음 gcd(a, b)로 나누면 끝.

 

정답코드를 보면서 이해해보자:

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

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

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

 

 

결과