[programmers] [Kotlin] 최대공약수와 최소공배수

문제 설명

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

 

제한 조건

• 두 수는 1 이상 1000000 이하의 자연수입니다.

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

코드

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var answer = intArrayOf(gcd(n,m), lcm(n,m))
        return answer
    }
    fun gcd(n:Int, m:Int):Int{
         return if(n < m){
            if(n == 0) m else gcd(n, m % n)
        }else{
            if(m == 0) n else gcd(m, n % m)
        }
    }
    fun lcm(n:Int, m:Int):Int{
        return (n * m) / gcd(n, m)
    }
}

풀이

유클리드 알고리즘(유클리드 호제법)은 두 수의 최대공약수를 구하는 알고리즘이다.

알고리즘 진행:

1. 두 수 n, m이 있고 n < m 인 관계이다.
2. m을 n으로 나눈 나머지를 k 라고 할 때, k가 0이게 되면 n이 최대 공약수이다. k가 0이 아니면 n보다 더 큰 수가 m을 나누어 떨어지게 할 수 있으므로 최대공약수가 될 수 없다.
3. 2번을 토대로 k가 0이 아니라면, m을 n값으로 치환하고, n을 k값으로 치환한 후, 2번 과정을 반복하여 나머지가 0이 될 때까지 수행한다.

이렇게 m, n 값을 바꾸어주면서 초기 m 값을 나누어 떨어지게 할 수 있는 값을 찾을 수 있게된다.

 

최소공배수는 두 자연수의 배수 중 공통인 것 중 가장 작은 것을 뜻한다.

최소공배수는 성질이 있어 최대공약수만 알면 바로 구할 수 있다

최소공배수는 두 수의 곱에서 최대공약수를 나눈 것과 같다.

 

결과

안정적으로 통과한 것을 볼 수 있다.