03/29 알고리즘 공부(81) - N개의 최소공배수

조건

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한조건

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

알고리즘 예상

1. 39번 문제 - 최대공약수와 최소공배수를 해결했던 알고리즘을 생각해보면 최대공약수를 먼저 구해서 최소공배수를 구했다. 
2. 유클리드 호제법이라는 공약수 구하는 방법을 이용해서 앞의 수 부터 최소 공배수를 구한 다음 그 결과물과 다음 수의 최소공배수를 구하는것을 반복한다.
3. 반복문이 끝나면 마지막 최소 공배수를 return한다.

 

초기 코드

class Solution {
    fun solution(arr: IntArray): Int {
        var answer = 0
        return answer
    }
}

 

내 코드

// 통과
class Solution {
    fun solution(arr: IntArray): Int {
        var lcm = 1
        
        for (i in arr){
            lcm = (i * lcm) / gcd(i, lcm)
            println(lcm)
        }
        
        return lcm
    }

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

꼬리재귀함수를 이용했다.

다른 사람의 풀이

class Solution {
    fun solution(arr: IntArray): Int {
        var answer = 1
        while(true) {
            var x = 0
            for(a in arr) x += answer%a
            if(x==0) return answer
            answer++
        }
        return answer
    }
}

 

개선점 또는 배운점

1. answer를 1씩 늘려가면서 최대 공약수를 찾지 않고 바로 최소 공배수를 찾았다.