[ 프로그래머스 - Kotlin ] N개의 최소공배수 ( 코틀린 )

( 연습문제 / 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

---

[풀이]

해당 문제는 유클리드 호제법을 이용하여 최소 공배수(lcm)를 구하면 됩니다.

두 숫자의 곱을 최대 공약수(gcd)로 나누어 가며 모두 수행하면 됩니다.

 

num1과 num2의 최소 공배수를 구할 경우, num1 = A * B이고 num2 = B * C라고 가정

lcm(num1, num2) = num1 * num2 / gcd(num1, num2)

                               = A * B * B * C / B

                               = A * B * C

 

위와 같은 과정을 위해 최대 공약수를 구하는 gcd 함수와 최소공배수를 구하는 lcm 함수를 구현하여 arr의 원소들을 차례로 넣어주면 됩니다.

---

[주의]

처음에는 무작정 1부터 n까지 나누어 0이 되는 지를 확인하였지만 조금만 검색을 해보니 최소공배수 문제는 유클리드 호제법으로 풀이하는 것을 알게 되었습니다.

물론 arr길이가 15 이하이고 원소도 100 이하이지만 유클리드 호제법을 사용하면 훨씬 간단하게 풀이할 수 있으니 기억해두면 좋을 것 같습니다.

---

[코드]

class Solution {
    fun solution(arr: IntArray): Int {
        var answer = arr[0]
        arr.forEach{ answer = lcm(answer, it) }
        return answer
    }
    
    fun lcm(a:Int, b:Int) = a * b / gcd(a, b)
    
    fun gcd(a:Int, b:Int):Int{
        return if (a < b){
            if (a == 0) b else gcd(a, b % a)
        }
        else{
            if (b == 0) a else gcd(b, a % b)
        }
    }
}

문제 링크

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

제가 잘못 알고 있거나 잘못된 부분이 있을 경우 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄