[Swift] 프로그래머스(lv.1) 18 - 최대공약수와 최소공배수

최대공약수와 최소공배수

문제 설명

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

제한 사항

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

 

 

 

문제 풀이

1. 최대 공약수를 구하기 위해 유클리드 호제법 알고리즘을 사용한다
2. 최소공약수를 구하는 알고리즘 `n * m / n과m의 최대공약수' 을 사용한다. 

 

 

 

코드

재귀 함수 사용

func solution(_ n:Int, _ m:Int) -> [Int] {
    
    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)
    }
    
    let result = [gcd(n,m), lcm(n,m)]
    
    return result
}

 

재귀 함수 미사용 (반복문 사용)

func solution(_ n:Int, _ m:Int) -> [Int] {
    
    func gcd(_ a:Int, _ b:Int) -> Int {
        var x = a
        var y = b
        
        while(y != 0) {
            var n = x%y
            x = y
            y = n
        }
        return x
    }
    
    func lcm(_ a:Int, _ b:Int) -> Int {
        return a * b / gcd(a,b)
    }
    
    let result = [gcd(n,m), lcm(n,m)]
    
    return result
}

인자로 들어오는 a와 b를 바꿔줘야 한다.

인자는 항상 상수이므로 새로운 변수 x,y 를 선언해야 한다.

이 때문에 가독성이 조금 안 좋아진다.

 

 

 

후기

오랜만에 최대 공약수, 최소 공배수 문제를 풀려고 하니까 알고리즘이 기억 안났다.

연습하면서 알고리즘을 외워나가자