[프로그래머스][Lv.2][JAVA]N개의 최소공배수

 

문제

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

제한 사항

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

입출력 예

 

---

 

분석

1. 2개의 숫자 a, b의 최소공배수를 구하는 공식
   : a * b / (a, b의 최대공약수)
2. 2개의 숫자 a, b의 최대공약수를 구하는 방법
   (1) BigInteger.gcd 함수 이용
           BigInteger b1 = BigInteger.valueOf(a);
           BigInteger b2 = BigInteger.valueOf(b);
           BigInteger gcd = b1.gcd(b2);
           return gcd.intValue();
   (2) 유클리드호제법으로 직접 구현 : 자세한 코드는 하기 참조 

 

### 유클리드 호제법을이용한 최대공약수를 구하는 코드

 

public class GCDExample {

    // 유클리드 호제법을 이용한 최대공약수 계산
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        int a = 24;
        int b = 36;

        int gcdValue = gcd(a, b);
        System.out.println("최대공약수: " + gcdValue); // 결과: 12
    }
}

 

---

 

피드백

1. 솔직히 AI의 도움을 많이 받았다. 최소공배수를 구하는 법, 최소공배수를 구하기 위해 필요한 최대공약수를 구하는 법 등. 알고리즘이 어렵다기보단 아마 이런 별도의 도움 없이 바로바로 수학적으로 풀어낼 수 있느냐가 중요해서 레벨 2인 걸까.

 

 

 

---

 

답안

class Solution {
    public static int solution(int[] arr) {
        int answer = 0;
        answer = arr[0];
        for(int i = 1; i < arr.length; i++) {
        	answer = lcm(answer, arr[i]);
        }
        return answer;
    }
    
    // 최대공약수를 통해 최소공배수 계산
    public static int lcm(int a, int b) {
    	return (a * b) / gcd(a, b);
    }

    // 유클리드 호제법을 이용한 최대공약수 계산
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

 

 

 

---

 

다른 사람의 답안

// 문제가 개편되었습니다. 이로 인해 함수 구성이나 테스트케이스가 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.
// 새로운 함수 구성을 적용하려면 [코드 초기화] 버튼을 누르세요. 단, [코드 초기화] 버튼을 누르면 작성 중인 코드는 사라집니다.

class NLCM {
    public long nlcm(int[] num) {
        long answer = num[0], g;
        for (int i = 1; i < num.length; i++) {
            g = gcd(answer, num[i]);
            answer = g * (answer / g) * (num[i] / g);
        }
        return answer;
    }

    public long gcd(long a, long b) {
        if (a > b)
            return (a % b == 0) ? b : gcd(b, a % b);
        else
            return (b % a == 0) ? a : gcd(a, b % a);
    }

    public static void main(String[] args) {
        NLCM c = new NLCM();
        int[] ex = { 2, 6, 8, 14 };
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(c.nlcm(ex));
    }
}

 

 

 

 

 

 

---

 

🔗링크

프로그래머스