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

👆문제풀러 가기👆

 

문제 설명

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

 

제한 사항

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

 

입출력 예

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

---

풀이 [ 메모리: 16,793kb, 최대시간: 0.03ms ]

func solution(_ n:Int, _ m:Int) -> [Int] {
    var divisor = 2
    var gcd = 1
    var (n, m) = (n, m)

    // 최대공약수 = 나누어떨어지는 수의 곱
    // 최소공배수 = 최대공약수 * (최대공약수로 나눈 몫)
    while true {
        // 나눌 값이 두 수의 최솟값보다 크면 함수 종료
        if divisor > min(n, m) { break }
        
        // n, m 나눠 떨어지는 divisor 구하기
        if n % divisor == 0 && m % divisor == 0 {
            n /= divisor
            m /= divisor
            
            // 최대공약수 = 나누어 떨어지는 수의 곱
            gcd *= divisor
            continue
        }
                
        divisor += 1
    }
    
    // 답: 최대공약수, 최소공배수
    return [gcd, gcd * (n * m)]
}

 

수학적 풀이를 그대로 코드로 구현해봤다.

나중에 알고보니 최소공배수와 최대공약수를 구하는 나름 정해진(?) 방식이 있었지만,, 기억이 안 났으니..

 

다른 풀이1 (유사 풀이)

func solution(_ n:Int, _ m:Int) -> [Int] {
    var gcd = 1
    
    for i in 1...min(n, m) {
        if n % i == 0 && m % i == 0 {
            gcd = i
        }
    }
    
    return [gcd, (n * m) / gcd]
}

 

다른 풀이2 [ 메모리: 16,793kb, 최대 시간: 0.02ms]

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

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