[Algorithm] N개의 최대공약수, 최소공배수 - 유클리드 호제법, Kotlin

프로그래머스 문제를 풀다가 정리가 필요할 것 같아서 정리한다.

https://programmers.co.kr/learn/courses/30/lessons/12953 

코딩테스트 연습 - N개의 최소공배수

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

입출력 예

arr                                                                                                result

[2,6,8,14]	168
[1,2,3]	6

 

문제 풀이

먼저 이 문제를 풀 때 유클리드 호제법이라는 알고리즘을 알아야 한다. 

예시

두 수 A = 4와 B = 8이 있다. A%B -> 4이고 B%A -> 0이다. 두 수를 나눈 나머지가 4와 0 인데  나머지가 0 이되었을 때 나누는 수가 최대 공약수이다.

즉 A%B의 결과값으로 B를 나누고 또 나온 결과값으로 ~~  코드로 말하자면

fun gcd(a: Int, b:Int): Int {
    var A = a // 4
    var B = b // 8
    while(B >0) { // 나머지가 0이 될 때까지
        var tmp = B // tmp에 8삽입 / tmp에 4삽입  
        B = A%B // B = 4          / B = 0 -> 나머지가 0 이됬으므로 4가 최대 공약수
        A = tmp // A = 8          / A = 4
    }
    return A
}

자 ,, 처음엔 모든 수의 최대 공약수를 구한 뒤, 최소 공배수를 구하면서 나눴는데 이러면 2,3,4의 최소 공배수는 24가 나오는 현상이 나타난다.

가장 중요한 건 두 수의 최대 공약수를 구하면서 최소 공배수 까지 구해줘야 한다! 

 

코드

fun main() {
    solutionazq(intArrayOf(2,3,4))
}
fun solution(arr: IntArray): Int {
    var answer = arr[0] // 배별의 첫 번째 원소를 담는다.
    arr.sort() // 배열 정렬
    for(i in 1 until arr.size) {
       var gcd = gcd(answer,arr[i]) // 첫 번째 원소와 두 번째 원소의 최대 공약수를 구하고
        answer *= arr[i] / gcd // 첫 번째 원소와 두 번째 원소의 곱을 최대 공약수로 나눠준다. 반복
    }
    return answer
}

fun gcd(a: Int, b:Int): Int {
    var A = a
    var B = b
    while(B >0) {
        var tmp = B
        B = A%B
        A = tmp
    }
    return A
}