10월 23일 - 최대공약수와 최소공배수 swift

문제 설명

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

 

제한 조건

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

 

내 답안

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

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

 

접근 방법

최대공약수 구하기 - 유클리드 알고리즘

1. 두 수 a와 b (a > b)가 주어지면, a를 b로 나눈 나머지를 구한다.
2. 이 나머지를 새로운 b로 하고, 원래의 b를 새로운 a로 한다.
3. b가 0이 될 때까지 이 과정을 반복
4. b가 0이 되었을 때의 a가 두 수의 최대공약수(GCD)입니다.

 

최소공배수 구하기 

두 수 곱하기 / 최대공약수 

 

다른 풀이

func solution(_ a: Int, _ b: Int) -> [Int] {
    var gcd = 1
    var lcm = a * b
    
    // 두 수 중 작은 수까지의 모든 수에 대해 최대공약수와 최소공배수를 검사
    let minAB = min(a, b)
    
    for i in 2...minAB {
        if a % i == 0 && b % i == 0 {
            gcd = i // 최대공약수 갱신
        }
    }
    
    lcm /= gcd // 최소공배수 계산
    
    return [gcd, lcm]
}

 

소인수분해 방법으로 최대공약수, 최소공배수를 구하는 방법

 

알게 된 것

유클리드 알고리즘

 

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

프로그래머스