프로그래머스 - N개의 최소공배수 java

12953

---

풀이

📌최소공배수 구하는 방법은 두 가지 방법이 있습니다.

1. 최대공약수를 이용하는 방법

2. 소인수분해를 이용하는 방법

 

두 가지 방법으로 풀어보겠습니다.

 

 

📝풀이1 (최대공약수 이용)

public int solution(int[] arr) {
	int lcm = arr[0];
	
	for(int i=1; i<arr.length; i++) {
		lcm = getLcm(lcm, arr[i]);
	}
	
	return lcm;
}

public int getGcd(int a, int b) {
	int tmp;
	while(b != 0) {
		tmp = b;
		b = a % b;
		a = tmp;
	}
	
	return a;
}

public int getLcm(int a, int b) {
	return a * b / getGcd(a, b);
}

📌최대공약수는 유클리드 호제법을 활용하여 구합니다. (이전 글 참고)

프로그래머스 - 최대공약수와 최소공배수, 유클리드 호제법 java

📌\( 최소공배수(a,b) = \frac{\left |ab \right|}{최대공약수(a,b)} \) 

 

🎈getGcd(int a, int b) : 유클리드 호제법을 이용해 최대공약수를 구합니다.

🎈getLcm(int a, int b) : 최대공약수를 활용한 방법으로 최대공배수를 구합니다. 

 

모든 수를 순회하며 최소공배수를 계속 구하면 배열의 모든 요소의 최소공배수를 구할 수 있습니다.

🔨public BigInteger gcd(BigInteger val) : 참고로 자바에는 최대공약수 구하는 메소드가 따로 있어요. 

⚡테스트 케이스 처리속도: 0.01ms ~ 0.02ms

 

 

📝풀이2 (소인수분해 이용)

public int solution(int[] arr) {
	int lcm = arr[0];
	
	for(int i=1; i<arr.length; i++) {
		lcm = getLcm2(lcm, arr[i]);
	}
	return lcm;
}

public int getLcm(int a, int b) {		
	Map<Integer, Integer> pf1 = getPrimeFactorization(a);
	Map<Integer, Integer> pf2 = getPrimeFactorization(b);
	
	for(int key : pf1.keySet()) {
		if( pf2.containsKey(key) ) {
			pf2.put(key, Math.max(pf1.get(key), pf2.get(key)));
		} else {
			pf2.put(key, pf1.get(key));
		}
	}
	
	int lcm = 1;
	for(int key : pf2.keySet()) {
		lcm *= Math.pow(key, pf2.get(key));
	}
	
	return lcm;
}

public Map<Integer, Integer> getPrimeFactorization(int num) {
	Map<Integer, Integer> map = new HashMap<>();
	for(int i=2; i<=Math.sqrt(num); i++) {
		while( num % i == 0 ) {
			map.put(i, map.getOrDefault(i, 0) + 1);
			num /= i;
		}
	}
	if( num != 1 ) {
		map.put(num, map.getOrDefault(num, 0) + 1);
	}
	
	return map;
}

📌두 수를 소인수분해 하여, 각 차수가 큰 값을 기준으로 모두 곱하면 최소공배수가 됩니다.

\( 10 = 2 * 5 \)

\( 12 = 2^{2} * 3 \)

각 차수가 가장 큰 값들을 모두 가져오면 => \( 2^{2}, 3, 5 \)

모두 곱한 값이 최소공배수이므로 60입니다.

 

🎈getPrimeFactorization(int num) : num을 소인수분해 해서 map에 담아 반환합니다.

🎈getLcm(int a, int b) : 두 수의 소인수분해된 map을 가져와 하나의 map으로 합칩니다. 이 때 차수가 더 큰 값을 찾아 map에 합칩니다.

합쳐진 map을 순회하며 모두 곱해서 최소공배수를 반환합니다.

 

⚡테스트 케이스 처리속도: 0.12ms ~ 0.35ms

---

References

🎈최소공배수

최소공배수 - 나무위키 (namu.wiki)

최소공배수 - 나무위키

🎈소인수분해

소인수분해 - 나무위키 (namu.wiki)

소인수분해 - 나무위키