• N개의 최소공배수

darklight

sublimevimemacs

Java

문제 설명

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

제한 사항

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

입출력 예

Untitled

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0]; // 첫 값은 0번 index 값
        
        for(int i = 1; i < arr.length; i++){ // 0번 index는 이미 사용했기에 1부터 시작
            int gcd = gcd(answer, arr[i]); // answer과 해당 index값과의 최대공약수 계산
            answer = answer * arr[i] / gcd; // answer 은 (answer * 해당 값) / 최대공약수
        }
        
        return answer;
    }
    
    private int gcd(int a, int b){ // 최대공약수
        int x = Math.max(a, b); // x는 매개변수 중 큰 값
        int y = Math.min(a, b); // y는 매개변수 중 작은 값
        
        while(x % y != 0){ // x % y == 0이 될 떄까지 반복
            int r = x % y; // r은 나머지
            x = y; // x는 y값
            y = r; // y는 r값
        }
        
        return y; // return y
    }
}