[Swift] 알고리즘 공부 - 최대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

 

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

 

 

설명

1. 최대공약수는 1부터 n이나 m중 하나를 골라 한번씩 n과 m의 모두 나누어 떨어지는지 확인

2. 나누어 떨어지는 수중 가장 큰값이 최대공약수

3. 최소공배수는 n과 m을 최대공약수로 모두 나눈수를 곱한뒤 최대공약수를 곱해주면 최소공배수

func solution(_ n:Int, _ m:Int) -> [Int] {
    
    var min = 0
    var max = 0

    max = (1...n).filter { n % $0 == 0 && m % $0 == 0 }.max()!
    min = (n / max) * (m / max) * max
    
    return [max, min]
}

 

찾아보니 최대공약수 최소공배수를 간단히 푸는 방법은 유클리드 호제법을 사용하면 간단하게 풀수 있다고 한다.

밑에는 다른사람의 풀이다. 

/// 최대공약수
func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    } else {
        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] {
    return [gcd(n, m), lcm(n, m)]
}