[Programmers] N개의 최소공배수 (유클리드 호제법)

 

- 목차

 

문제 설명.

문제 설명

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

제한 사항

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

입출력 예

[2,6,8,14]	168
[1,2,3]	6

 

 

문제 분석.

제공된 모든 수의 최소공배수를 계산하는 문제입니다.

저는 두 수를 곱하고 두 수의 최대공약수를 나누는 방식을 사용하였습니다.

그리고 최대공약수는 유클리드 호제법을 사용하여 계산하였습니다.

  int findGCM (int a, int b) {
    int gcd = findGCD(a, b);
    return a * b / gcd;
  }
  int findGCD (int a, int b) {
    int max = Math.max(a, b);
    int min = Math.min(a, b);
    int remainder = max % min;
    while (remainder != 0) {
      max = Math.max(remainder, min);
      min = Math.min(remainder, min);
      remainder = max % min;
    }

    return min;
  }

 

 

문제 풀이.

class Solution {
  public int solution(int[] arr) {
    int answer = arr[0];
    for (int i = 1; i < arr.length; i++) {
      answer = findGCM(answer, arr[i]);
    }
    return answer;
  }

  int findGCM (int a, int b) {
    int gcd = findGCD(a, b);
    return a * b / gcd;
  }
  int findGCD (int a, int b) {
    int max = Math.max(a, b);
    int min = Math.min(a, b);
    int remainder = max % min;
    while (remainder != 0) {
      max = Math.max(remainder, min);
      min = Math.min(remainder, min);
      remainder = max % min;
    }

    return min;
  }
}