(알고리즘) 최대공약수와 최소공배수 구하기

신나는 주말!

주말에는 간단한 알고리즘 문제를 풀어보자!

 

🔥알고리즘 문제

 

문제 설명

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

제한 사항

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

 

입출력 예

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

입출력 예 설명

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

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

 

내가 작성한 코드 

fun solution(n: Int, m: Int): IntArray {
    val bestnumber = mutableListOf<Int>()
    val bestnumber2 = mutableListOf<Int>()

    for (i in 1..n) {
        if (n % i == 0) {
            bestnumber.add(i)
        }
    }
    for (i in 1..m) {
        if (m % i == 0) { 
            bestnumber2.add(i)
        }
    }

    var thebestnumber = 1

    for (i in 0 until bestnumber.size) {
        for (j in 0 until bestnumber2.size) {
            if (bestnumber[i] == bestnumber2[j]) {
                if (thebestnumber < bestnumber[i]) thebestnumber = bestnumber[i]
            }
        }
    }

    // 최소 공배수 구하기
    var leastnumber = n * m
    for (i in 1..m) {
        for (j in 1..n) {
            if (n * i == m * j) {
                if (leastnumber > m * j) leastnumber = m * j
            }
        }
    }

    return intArrayOf(thebestnumber, leastnumber)
}

 

내가 작성한 코드 해석

1. intArrayOf(thebestnumber, leastnumber) : 최소공배수와 최대공약수를 따로따로 구해서 intarrayof()의 요소 안에 저장함

2.최대공약수를 구하는 과정에서 n과m의 약수를 각각의 리스트에 저장하고 n과m에 저장된 약수의 리스트를 서로 비교하여 일치하는 값중 가장 큰 값을 최대공약수로 설정 -> for문을 2중 중첩하여 모든 값에 접근해서 비교를 하게끔 설계

3. 최소 공배수는  최소 공배수의 값은 n*m 값 이하가 되야하므로 var leastnumber = n * m 값으로 초기화 후 마찬가지로 for문 2중 중첩을 이용해서 n의 배수값과 m의 배수값중 일치하는 값중 가장 작은 값을 leastnumber로 저장함

4. 최종적인 최대공약수 값과 최소공배수 값을 intArrayOf()안에 담은 후 return함 

 

다른사람은 어떻게 했을까?

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)
} // 박*우 , ql***p@gmail.com , *진 , 류*형 님의 코드입니다

 

다른 사람들이 작성한 코드 해석

1. tailrec fun gcd(a: Int, b: Int):Int= if (b ==0) a else gcd(b, a % b) -> gcd함수를 정의 

2. tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
두 정수 a와 b를 인수로 받고 만약 b가 0이라면, 이때 a가 최대공약수
(어떤 수와 0의 최대공약수는 자기 자신이기 때문) 

3. tailrec fun gcd(a: Int, b: Int): Int =if (b == 0) a else gcd(b, a % b)
그렇지 않은 경우, b와 a를 b로 나눈 나머지(a % b)를 매개변수로 받는 gcd()함수를 실행함.  여기서 a는 b보다 큰 값이 됨. 그리고 이 과정을 반복하여 재귀적으로 최대공약수를 찾음

4.tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) a  else gcd(b, a % b): 
tailrec 키워드를 이용해서 재귀 호출이 꼬리 위치에서만 일어날 때, 즉 함수의 마지막 작업으로서 호출되는 경우에는 스택을 추가로 사용하지 않고 반복문으로 변환하여 성능을 향상 시킬 수 있음

5. val gcd = gcd(n, m) : n과m의 최대공약수를 gcd라는 변수에 저장함 즉 gcd=최대공약수

6. return intArrayOf(gcd, n * m / gcd):
최소공배수는 두 수를 곱한 후 최대공약수로 나눈 값이므로 최소공배수 값은 n * m / gcd

7. return intArrayOf(gcd, n * m / gcd ): 최대공약수와 최소공배수의 값을 담은 배열 반환

 

어떻게 이런 코드를?!

재귀호출을 이용하는것은 머리 아프다....

 

 

 

더 개선해야할 Point

똑같은 기능을 구현하는데 나는 10줄이 넘는 코드를 작성한 반면 다른사람은 3줄의 코드로 작성한 것을 보면 아직 알고리즘에 대해서는 공부해야할것이 많다고 느껴진다.

내가 작성한 코드의 시간복잡도와 공간 복잡도는

시간 복잡도: O(n*m)

공간 복잡도: O(n+m) 

 

다른 사람이 작성한 코드의 시간복잡도와 공간 복잡도

시간 복잡도: O(log(min(n,m)))

공간 복잡도: O(1)

 

단순히 코드의 양뿐만 아니라 복잡도 부분에서도 후자의 코드가 더 뛰어나니 나의 코드에서 개선의 필요가 느껴진다

 알고리즘 GitHub :https://github.com/kotlin2024/algorithm/commit/25b961b2cc71da6ffaf8008932d8e4524cce3807