[문풀] 최대공약수와 최대공배수

⚙️ 최대공약수, 최소공배수

최대공약수는 입력된 숫자보다 작을 것이므로 반복문을 사용하면 될것이다. 최소공배수도 같은 원리로 입력된 수와 같거나 그 이상일 것이므로 반복문을 사용하면 될것이다. 구현해 보면

func solution(_ n:Int, _ m:Int) -> [Int] {
    //최대공약수
    var min = n < m ? n : m
    while true {
        if n % min == 0 && m % min == 0{
            break
        }
        min += 1
    }
    //최소공배수
    var max = n > m ? n : m
    while true {
        if max % n == 0 && max % m == 0{
            break
        }
        max += 1
    }
    
    return [min, max]
}

이렇게 구현했더니 testCase 2번째에서 최대공약수를 찾지 못하였다. 생각해보니 위의 코드는 두 수가 배수 관계에 있어야지만, 즉 두 수의 최대공약수가 1이 아닐때만 성립하는 코드였다. 그래서 아래와 같이 수정하였다.

func solution(_ n:Int, _ m:Int) -> [Int] {
   var min = n > m ? n : m
    while true {
        if n % min == 0 && m % min == 0{
            break
        }
        min -= 1
    }
    var max = n > m ? n : m
    while true {
        if max % n == 0 && max % m == 0{
            break
        }
        max += 1
    }
    
    return [min, max]
}

이렇게 풀었더니 성공했다.

다른사람들의 풀이를 보니 수학적인 지식을 활용한 풀이가 많았다.

func solution(_ n:Int, _ m:Int) -> [Int] {
    var first: [Int] = []
    for index in 1...n {
        if n % index == 0  && m % index == 0 {
            first.append(index)
        }
    }
    let maxValue: Int = first[first.count-1]
    return [maxValue ,(n * m)/maxValue ]
}

이 풀이에 의하면 어떤 수의 최소공배수는 두 수의 곱을 최대공약수로 나눈 값이였다.