N개의 최소공배수(2레벨)

class Solution {
    fun solution(arr: IntArray): Int {
        var answer = 0
        var number1 = 0 
        var number2 = 0
        var temp = 0
        var gcd = 0 //최대 공약수
        var lcm = 0 //최소 공배수
        for(i in 0 until arr.size-1)
        {
            if(arr[i] >= arr[i+1]) //대수 비교
            {
                number1 = arr[i]
                number2 = arr[i+1]
            }
            else
            {
                number1 = arr[i+1]
                number2 = arr[i]
            }
            while(number1%number2!=0)
            {
                temp = number2
                number2 = number1 % number2
                number1 = temp
            }
            gcd = number2
            lcm = arr[i] * arr[i+1] / gcd
            
            arr[i+1] = lcm
        }
        answer = arr[arr.size-1]
        return answer
    }
}

이번 문제는 학창시절 소인수분해를 통해 구하던 방식으로 구현할려니 많이 복잡해져서

인터넷을 찾아보니 컴퓨터 코딩으로 구현하기에 적합한 유클리드 호제법을 통해 구현하였다.

유클리드 호제법은

간단하게 말하면 나머지가 0이 나올 때까지 나머지 연산을 하면 최대 공약수를 구할수 있는 법칙이다.

 

큰수 mod 작은수 = 나머지1
작은수 mod 나머지1 = 나머지2

 

이런식으로 반복하면 언젠가는 무조건 나머지가 0이 나오게 되는데

이때 나머지가 0이 되게 한 나눈 수가 최대 공약수가 된다.

 

유클리드 호제법을 통해 최대공약수를 구한다음

두 수의 곱 = 최대 공약수 x 최소 공배수

공식을 통해 최소 공배수를 구하면 된다. 

 

해설

반복문을 돌려  i 와 i+ 1 두 개의 arr 요소를 가져온다.
유클리드 호제법을 활용해 두 수의 최소 공배수를 구한다.
i +1에 최소 공배수를 집어 넣는다.
두 수의 최소 공배수의 다른 수 최소 공배수는
세 수의 최소공배수와 동일하다.
그렇기 떄문에 이를 반복 할시 n 개 수의 최소 공배수를 구할 수 있다.