[Programmers] N개의 최소공배수

🔒 문제

💡 생각의 흐름

(1) 아, 유클리드 호제법 GCD (최대공약수) 함수 작성해서 최소공배수 바로 구해보리기 하면 되겠군.

최대공약수 공식 알고리즘은 요기서

최대공약수 알고리즘

(2) 오름 정렬해서 쪼꼬만 애들끼리 만든 최소공배수로 뒷놈들 다 검사해보는 식으로 해야겠군

 

🔑풀이 (Kotlin)

class Solution {
    fun gcd (a: Int, b: Int) : Int {
        var bigger = a
        var smaller = b
        while (smaller != 0) {
            val remainder = bigger % smaller
            bigger = smaller
            smaller = remainder
        }
        return bigger
    }
    fun lcm (a: Int, b: Int) : Int {
        return a * b / gcd(a, b)
    }
    fun solution(arr: IntArray): Int {
        arr.sort()
        var answer = arr[0]
        for (index in 0..arr.size - 2) {
            if (answer % arr[index+1] != 0) answer = lcm(answer, arr[index+1])
        }
        return answer
    }
}