[프로그래머스/Lv.2] N개의 최소공배수(+유클리드 호제법) - Kotlin

📌 문제

프로그래머스

📌 유클리드 호제법을 이용해 최대공약수(GCD) 구하기

이 문제를 풀기 전에 먼저 유클리드 호제법을 배우면 좋다. 유클리드 호제법이란 최대공약수(GCD, Greatest Common Divisor)를 찾는 효율적인 알고리즘이다. 유클리드 호제법은 두 정수 a와 b(단, a > b)의 최대공약수를 구할 때, 다음과 같은 사실을 이용한다.

GCD(a, b) = GCD(b, a % b)

이 과정을 나머지가 0이 될 때까지 반복하며, 나머지가 0이 되면 그때의 b가 두 수의 최대 공약수가 된다.

유클리드 호제법을 이용해 최대공약수를 구해보자!

1. a = 56, b = 42
2. GCD(56, 42) = GCD(42, 56 % 42) 이므로 a = 42, b = 14이다.
3. GCD(42, 14) 에서 42 % 14은 0이므로 현재 b의 값인 14가 최대공약수가 된다. 

그럼 이 과정을 코틀린 코드로 적어보자. b가 0일 경우, a의 값이 그 이전의 b의 값이므로 a를 반환한다.

fun gcd(a: Int, b: Int): Int = if (b != 0) gcd(b, a % b) else a

📌 유클리드 호제법을 이용해 최소공배수(LCM) 구하기

유클리드 호제법으로 구한 최대공약수(GCD)를 이용해 두 수의 최소공배수(LCM, Least Common Multiple)도 구할 수 있다. 최소공배수는 두 수의 곱을 그들의 최대공약수로 나눈 값이다.

LCM(a, b) = (a * b) / GCD(a, b)

유클리드 호제법을 이용해 최대공약수를 구한 후, 최대공약수를 이용해 최소공배수를 구해보자!

1. a = 56, b = 42
2. 위에서 유클리드 호제법으로 GCD(56, 42) = 14라는 것을 알게 되었으니 슬쩍 가져와서 최소공배수를 구한다. LCM(56, 42) = (56 * 42) / 14 = 2352 / 14 = 168
3. 따라서 56과 42의 최소공배수는 168이 된다.

이 과정을 코틀린 코드로 적어보자.

fun lcm(a: Int, b: Int) = (a * b) / gcd(a, b)

 

이렇게 최대공약수 & 최소공배수 키워드가 나온다면 유클리드 호제법을 기억하자! 👀

📌 풀이

이제 유클리드 호제법을 이용해 문제를 풀면 되는데, 두 수의 최소공배수가 아닌 N개의 최소공배수를 구해야 한다. 하지만 배운걸 그대로 이용하면 된다. 먼저 위에서 적은 코틀린 코드를 그대로 적어준다.

fun gcd(a: Int, b: Int): Int = if (b != 0) gcd(b, a % b) else a // 최대공약수 구하기
    
fun lcm(a: Int, b: Int) = a * b / gcd(a, b) // 최소공배수 구하기

 

 예시를 보면 arr = [2, 6, 8, 14] 이 주어지는데, arr[0]부터 순회하며 모든 요소에 대한 최소공배수를 구해야한다는 것을 알 수 있다. answer를 arr[0]으로 설정한 후, forEach문을 돌며 비교해나갔다.

fun solution(arr: IntArray): Int {
    var answer = arr[0]
    arr.forEach { 
        answer = lcm(answer, it)
    }
    return answer
}

📌 전체 코드

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