[프로그래머스] N개의 최소공배수 - 자바(Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

 

문제 설명

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

 

 

제한사항

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

 

 

코드

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0]; // 배열의 첫 번째 원소 초기화

        // i = 1부터 반복
        for (int i = 1; i < arr.length; i++) {
            // 현재까지의 최소공배수와 현재 원소의 최대공약수 계산
            int gcd = gcd(answer, arr[i]);

            // 최소공배수 갱신
            answer = answer * arr[i] / gcd;
        }

        return answer;
    }

    // 최대공약수 계산 함수
    private static int gcd(int a, int b) {
        int x = Math.max(a, b);
        int y = Math.min(a, b);

        // 나누어 떨어지지 않을 때까지 반복
        while (x % y != 0) {
            int r = x % y;
            x = y;
            y = r;
        }

        return y;
    }
}

코드 설명

주석 참고

• 이 문제는 배열의 모든 요소들의 최소공배수를 구하는 문제로 유클리드 호제법을 활용할 수 있다.
• 유클리드 호제법은 서로 다른 두 숫자의 최대공약수를 구하는 방법으로 다음과 같은 과정으로 구할 수 있다.
  • ex) 큰 수 : 48, 작은 수 : 18
  • 큰 수(48)를 작은 수(18)로 나누어 나머지(12)를 얻는다.
  • 작은 수(18)에서 나머지(12)를 나누어 다시 나머지(6)를 얻는다.
  • 나머지가 0이 될 때까지 반복한다.
  • 나머지가 0이 된 순간 마지막으로 0이 아닌 나머지가 최대공약수가 된다. (이 경우 6이 최대공약수)
• 유클리드 호제법을 통해 얻은 최대공약수를 활용하여 문제를 풀 수 있다.
• arr[0]을 answer에 담은 뒤 i = 1부터 반복한다.
• 유클리드 호제법을 통해 answer와 arr[i]의 최대공약수를 구한다.
• answer에 answer와 최대공약수를 곱하여 최소공배수를 갱신한다.
• 반복문이 끝나면 answer에는 모든 배열에 대한 최소공배수가 구해진다.