[프로그래머스] 최대공약수와 최소공배수

문제 설명

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

제한 사항

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

입출력 예

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

입출력 예 설명

입출력 예 #1위의 설명과 같습니다.

입출력 예 #2자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

풀이

1) 최대공약수와 최소공배수 구하는 알고리즘을 몰랐음 구글링 Start !💻💻

😎 유클리드 호제법이란?

1. 최대공약수 구하기

(A > B 일 때)

A, B의 최대공약수(GCD : greatest common divisor)는 A를 B 로 나눈 나머지 r이 있을 때,

B와 r의 최대공약수와 같다.

2. 최소공배수 구하기

A * B / 최대공약수

유클리드호제법

2) 비전공으로 시작해서 그런지 머리가 안돌아간다 겨우 이해완료 갈 길이 멀다.

3) 기초는 언제나 중요한것 같다.

4) 재귀함수 풀이방식도 존재한다. (꼬리재귀 함수도 가능 이 부분은 보완해야함.)

5) 코드 내에서는 import kotlin.math.* 함수를 import해서 max, min 값을 도출하였다.

제출 코드

import kotlin.math.*

class Solution {
    fun solution(n: Int, m: Int): IntArray {                
        
        // 2개의 자연수의 큰 수와 작은수를 먼저 구함.        
        var max = max(n, m) // 큰 수
        var min = min(n, m) // 작은 수
    
        // 작은수(나누는 수)가 0이 될 때까지 반복
        while(min > 0){
            
            // 작은 수(나누는 수)의 임시 변수
            var temp = min
            
            // 나머지가 나누는 수가 된다.
            min = max % min
            
            // 작은수가 큰 수가 된다.
            max = temp                        
        }

        //println(max)
        //println(n*m/max)                
                
        return intArrayOf(max, n*m/max)
    }
}

가장 이해가 쉬운 코드같음

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

    // 최대공약수
    fun gcd(n: Int, m: Int): Int {
        var num1 = n
        var num2 = m

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

        return num1
    }

    // 최소공배수
    fun lcm(n: Int, m: Int): Int = n * m / gcd(n, m)
}

재귀함수

class Solution {
    fun solution(n: Int, m: Int) = intArrayOf(gcd(n, m), lcm(n, m))
    
    fun lcm(n:Int, m:Int) = n * m / gcd(n, m)
    
    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)
        }
    }
}

꼬리재귀 함수 (이해가 너무 어려움 갈 길이 멀다)

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)
}