02/07 알고리즘 공부(39) - 최대공약수와 최소공배수

조건

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.( 두 수는 1이상 1000000이하의 자연수입니다.)

알고리즘 예상

1. n의 약수를 찾는다.
2. n의 약수 중 최대 공약수 a를 찾는다.
3. n*m / a를 통해 최소 공배수를 찾는다.

 

초기 코드

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var answer = intArrayOf()
        return answer
    }
}

 

내 코드

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var answer = intArrayOf()
        var div = (1..n).filter{n%it == 0}
        var com_Div = div.filter{m%it == 0}
        
        answer += com_Div.maxOf{it}
        answer += n*m/com_Div.maxOf{it}
        
        return answer
    }
}

처음에는 위 알고리즘 예상대로 n의 약수를 먼저 뽑았지만 코딩하고 보니 한번에 해도 될 것 같았다.

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var answer = intArrayOf()
        var com_Div = (1..n).filter{n%it == 0 && m%it == 0}.maxOf{it}
        
        answer += com_Div
        answer += n*m/com_Div

        return answer
    }
}

이렇게 하고 보니 answer선언을 안해도 될 것 같아서 answer를 선언하지 않아 보았다.

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var com_Div = (1..n).filter{n%it == 0 && m%it == 0}.maxOf{it}
        return intArrayOf(com_Div, n*m/com_Div)
    }
}

코드 박스도 없엘 수 있을 것 같아 없에 보았다.

class Solution {
    fun solution(n: Int, m: Int): IntArray = intArrayOf((1..n).filter{n%it == 0 && m%it == 0}.maxOf{it}, n*m/(1..n).filter{n%it == 0 && m%it == 0}.maxOf{it})  
}

다만 이렇게 풀 경우 코드가 옆으로 엄청 길어지는 문제가 있다.

다른 사람의 풀이

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        val gcd = gcd(n, m)

        return intArrayOf(gcd, n * m / gcd)
    }

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

class Solution {
    fun solution(min: Int, max: Int): IntArray {
        var min = min
        var max = max
        var g = max * min
        var temp = 0
        while (min > 0) {
            temp = max % min
            max = min
            min = temp
        }
        return intArrayOf(max, g / max)
    }
}

개선점 또는 배운점

1. 앞에서 봤던 꼬리재귀함수를 사용한 풀이가 깔끔했다.
2. 함수를 두 개 이상 써서 푼 풀이가 많았다.
3. 최대 공약수의 변수명을 gcd(greatest common divisor)로 한 풀이가 굉장히 많았다.
4. 아래풀이는 최대공약수 구하는 방법이 신기했다.