프로그래머스 최대공약수와 최소공배수 코틀린

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

 

 

1. 최초아이디어

fun main() {

    var n = 24
    var m = 32
    var ndivisor = mutableListOf<Int>()
    var mdivisor = mutableListOf<Int>()


    for (i in 1..n) {
        if (n % i == 0) {
            println("${i}는 n의 약수입니다")
            ndivisor.add(i)
        }
    }

    for (i in 1..m) {
        if (m % i == 0) {
            println("${i}는 m의 약수입니다")
            mdivisor.add(i)
        }
    }

    println(ndivisor)
    println(mdivisor)

    var mindivisor: Int = 1


    for(i in ndivisor){
        if(i in mdivisor && i != 1){
            mindivisor = i
            break
        }
    }

    println(mindivisor)

}

해당 방법은 각 숫자의 약수를 구한 뒤 1을 제외한 첫 번째 공통된 숫자 = 최소공약수 를 구하는 방법이다.

이를 조금만 응용하면 최대공약수를 구할 수 있지만, 순간 이렇게까지 길어질 코드인가?에 대해 생각해보았다.

 

전혀 수학적이지 않고 원초적인 코드라는 이야기다.

 

해당 방법으로 공약수를 구해도 괜찮지만, 이를 수학적으로 간소화 시킬 방법이 없나 생각하는 도중 찾은것이

유클리드 호제법이다.

 

fun main() {

    var num1 = 24
    var num2 = 32
    var GCD = num1

    while (num2 != 0){
        val temp = num2

        num2 = GCD % num2
        GCD = temp
    }

    var LCM = num1 * num2/GCD

    println("최대공약수 ${GCD} 최소공배수${LCM}")


}
    
}

GCD는 최대공약수의 약자이고 LCM은 최소공배수의 약자다.

유클리드 호제법은 서로 계속 나눠서 나머지 값이 0될 때 까지 실행된다.

즉 서로를 계속 나눠서 0이 된다면 종료하고 그 값을 반환하면 최대공약수가 될 것이다.

 

    while (num2 != 0){
        val temp = num2
        num2 = num1 % num2
        num1 = temp
    }

 

여기서 재밌는점은 while문 안에 들어가는 두 수의 우열을 가릴 필요가 없다.

두 수 num1 과 num2가 들어간다고 쳤을 때

 

num2 > num1이라면

 

num1%num2 = num1

이므로

num2 = num1

num1 = temp(최초의 num2)

 

즉 num2와 num1이 교환되는 상황이 벌어져 다시 계산해서 옳바른 값을 만든다.

 

 

최소공배수 = 두 수의 곱 / 최대공약수

 

이는 지수분해를 통해 그 원리를 쉽게 이해할 수 있는데,

 

예를들어

 

24 = 2^3 * 3

32 = 2^3*2^2

 

최대공약수는 2^3
최소공배수는 2^3*2^2*3

즉

 

최소공배수 = 24( 2^3 * 3)*32(2^3*2^2)/GCD다

정답

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var num1 = n
        var num2 = m
        while(num2 != 0){
            var temp = num2
            num2 = num1%num2
            num1 = temp
        }
        var lcm = n*m/num1
        var answer = intArrayOf(num1,lcm)
        return answer
    }
}

참고 블로그

https://m.blog.naver.com/eandimath/221704180761

[최대공약수 쉽게 구하는 법]-유클리드 호제법