N개의 최소공배수

최소공배수 문제 풀러가기

프로그래머스

이번 문제는 N개의 숫자가 주어졌을 때 해당 수들의 최소공배수를 구하는 문제이다.

예를 들어 2,7의 최소공배수는 14라는것을 모두들 알 것이다.

 

해당 문제에서는 n개의 숫자가 담긴 int형 배열 arr이 제공된다.

기존에 알고있던 공식을 이용하여 문제를 풀어보았다.

 

ex > a,b라는 정수가 있는 경우

(ab의 최소공배수 = a * b / a,b의 최대공약수)  의 공식을 이용하여 풀어낼 수 있다.

하지만 이는 3개 이상의 수를 한번에 계산하는 방식으로는 옳지 못하다 판단하였다.

 

이에 해당하는 반례를 찾아보았다. 

{4,6,8} 이라는 값이 주어진 경우 해당 공식을 이용하여 문제를 풀게되면 

 

최소공배수 = 4*6*8 / 2 라는 값을 가지게 된다.

이렇게 되면 잘못된 최소공배수의 값인 96을 반환한다.

 

이러한 연유로 2개의 숫자씩 각각 계산을 하기로 결정하였다.

완성된 해당 코드는 이러하다.

 

public static int solution(int[] arr) {
    int lcmValue = arr[0];  // 최소공배수를 저장할 변수

    // 배열 내 모든 숫자에 대해 최소공배수 계산
    for (int i = 1; i < arr.length; i++) {
        lcmValue = lcm(lcmValue, arr[i]);
    }

    return lcmValue;
}

최소공배수를 저장할 lcmValue라는 변수를 하나 선언해 주었고 lcm이라는 메서드를 형성하여 실행시키도록 만들어주었다.

 

// 최소공배수(LCM) 구하기
private static int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

lcm메서드는 2개의 값을 이용하여 최소공배수를 구하는 공식을 적용한 메서드이다. 

해당 메서드에서 매개변수로 받아와지는 a,b 두값의 최대공약수를 구하기 위해 gcd라는 메서드도 구현하였다. 

 

// 최대공약수(GCD) 구하기 (유클리드 호제법)
private static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

기존 알고있던 공식을 검색해보니 lcm, gcd라는 이름이 붙여진 유클리드 호제법이라는 이름이 있었다.

해당 gcd메서드는 나머지가 0이 될때까지 나머지연산을 반복하여 두 값의 최대공약수를 구해내는 방식이다.

 

이렇게 간단한 지식 하나만으로 여러가지 수가 주어졌을 때의 최소공배수를 구하는 방법을 알아보았다.