N개의 최소공배수

문제정의

---

N개의 수가 주어지고 이 수 전체의 최소공배수를 구하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

package level2;

import java.math.BigInteger;

public class NNumLCM {

    //프로그래머스 문제풀이 Level2 n개의 최소공배수

    public static void main(String[] args) {
        int[] arr = {2, 6, 8, 14};
        if(arr.length == 1)
            System.out.println(arr[0]); 

        BigInteger n1 = new BigInteger(Integer.toString(arr[0]));
        BigInteger n2 = new BigInteger(Integer.toString(arr[1]));
        BigInteger gcd = n1.gcd(n2);
        n1 = n1.multiply(n2).divide(gcd);
        
        for(int i = 2; i < arr.length; i++)
        {
            n2 = new BigInteger(Integer.toString(arr[i]));
            gcd = n1.gcd(n2);
            n1 = n1.multiply(n2).divide(gcd);
        }
        int answer = Integer.parseInt(String.valueOf(n1));
        System.out.println(answer);
    }
    
}

1. 두 수의 곱은 두 수의 최소공배수와 최대공약수의 곱과 같다. 2. 최소공배수는 모두의 배수이다.

이 두 가지만 알면 문제를 풀 수 있다. 2번이 무슨 말이냐고 할 수 있는데, 코드에 나와있는 것을 예시로 들면 2와 6의 최소공배수는 12이고 12와 8의 최소공배수가 24이고, 24와 14의 최소공배수는 168이다. 즉, 최소공배수를 앞에 두개씩 구해나가다보면 그것이 모든 수의 최소공배수가 된다는 것이다. 최소공배수를 구하는 방법은 1번식을 활용하면 된다.

이제 코드를 보자. 배열의 길이가 1인 경우에는 공배수라는 개념이 없으므로 원소 하나를 프린트하면된다. 그렇지 않은 경우 두 수의 촤대공약수를 구해 두 수의 곱에서 나눠주는 과정을 반복하면 된다.

최종 시간복잡도는 arr의 길이를 n이라 할 때 \(O(nlog_{2}n)\)이다. 왜냐하면 n번 동안 gcd를 사용하기 때문인데, 정확한 시간복잡도는 나와있지 않지만, 두 수를 a,b라 할때 한 쪽의 절반보다 크냐 작냐에 따라 연산이 달라지므로 \(log_{2}n\)이라 생각한다.

테스트