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

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

프로그래머스

---

 

문제

 

 

풀이

n개의 수들의 최소공배수를 구하려면 앞에서부터 2개씩 최소공배수를 구하고, 그 다음은 구한 최소공배수와 그 다음 수의 최소공배수, ··· 를 반복합니다.

 

따라서 처음에는 arr[0]과 arr[1]의 최소공배수 result를 구합니다. 그 다음 2번째부터 n-1번째까지, result와 arr[i]의 최소공배수를 구합니다. 마지막까지 계산한 result가 n개의 최소공배수가 됩니다.

 

최소공배수를 구하는 방법은 큰 값의 배수가 작은 값의 배수가 될 때, 그 때의 배수가 최소공배수가 됩니다.

작은 값과 큰 값을 구분해야 하기 때문에 arr를 오름차순 정렬합니다.

두 수 x, y(x < y)에 대하여, (y * i)가 x로 나눠 떨어진다면 (y * i)가 x와 y의 공배수가 됩니다. 공배수들 중 가장 작은 값이 최소공배수이기 때문에 i를 1부터 하나씩 늘려가면서 계산해주고, (y * i)가 x로 나눠 떨어진다면 그 때의 (y * i)가 최소공배수가 될 것입니다.

 

 

소스코드

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        Arrays.sort(arr);
        
        int result = lcm(arr[0], arr[1]);
        
        for(int i=2; i<arr.length; i++){
            result = lcm(result, arr[i]);
        }
        
        return result;
    }
    
    public int lcm(int x, int y){
        int result = 0;
        
        int i = 1;
        while(true){
            if((y * i) % x == 0){
                result = y * i;
                break;
            }
            else{
                i ++;
            }
        }
        
        return result;
    }
}