[프로그래머스] N개의 최소공배수 (kotlin)

 

문제해결 point

두 수의 최대공약수 구하기 ->  유클리드 호재법 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

 

---

1. 유클리드 호재법을 사용하여 배열에 인접한 두 수의 최대공약수를 구한 뒤,

     (두 수의 곱 나누기 최대공약수= 최소공배수) 법칙을 이용하여 최소공배수를 구한다. 

2. 구해진 최소공배수를 answer에 반영하고 다음 3번째 인덱스와 반영된 answer의 최소공배수를 구한다. 

4. 이와 같은 방법으로 마지막 인덱스의 값과도 최소공배수를 구해 answer에 반영합니다.

 

전체코드

fun solution_l(arr: IntArray): Int {

    var answer = 1
    var gcd = 0

    if(arr.size==1){ //숫자가 하나 주어질 경우
        return arr[0]
    }

    gcd = gcd(arr[0], arr[1])
    answer = ((arr[0] * arr[1]) / gcd)

    if(arr.size==2){ // 숫자가 두개 주어질 경우
        return answer
    }

    for (i in 2 until arr.size) {
        gcd = gcd(arr[i], answer)
        answer = ((arr[i] * answer) / gcd)

    }
    return answer
}

fun gcd(a: Int, b: Int): Int {

    var r = a % b
    if (r == 0) {
        return b
    } else {
        return gcd(b, r)
    }
}