[프로그래머스][Level2][Java] N개의 최소공배수

 

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

코딩테스트 연습 - N개의 최소공배수

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[] arr) {
        int min = arr[0];
        
        for(int i=1; i<arr.length; i++) {
        	min = (min * arr[i]) / gcd(Math.max(min, arr[i]), Math.min(min, arr[i]));
        }
        return min;
    }
    
	static int gcd(int max, int min) {	
		while(min!=0) {
			int remainder = max%min;
			max =min;
			min = remainder;
		}
		return max;
	}
}

📝 정리

1. 유클리드 호제법으로 최대공약수를 구한다.
2. 최대 공배수 = 두수의 곱 / 두수의 최대공약수 이다.
3. 1부터 N개까지 반복한다.