문제
제출 코드
에라토스테네스 체로 소수를 구해낸 뒤, 각 숫자들을 소인수분해 하였다.
최소공배수는 모든 숫자들의 소인수를 포함하는 최소값이므로, 각 숫자의 소인수를 구해가며 제일 큰 값들만 저장하도록 했다.
각 소인수의 밑 부분(소수)를 key값으로, 지수 값을 value로 가지는 map으로 소인수 값을 관리했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;
class Solution {
public int solution(int[] arr) {
// 1. 소수 구하기
boolean[] notPrime = new boolean[101];
for(int i=2; i<=100; i++){
if(notPrime[i]) continue;
for(int j=2; i*j<=100; j++) notPrime[i*j] = true;
}
List<Integer> prime = new ArrayList<Integer>();
for(int i=2; i<=100; i++) if(!notPrime[i]) prime.add(i);
// 2. 소인수 구하기
Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
for(int num : arr){
Map<Integer, Integer> tmp = new TreeMap<Integer, Integer>();
for(int p : prime){
if(num < p) break;
int cnt = 0, now = num;
while(true){
if(now%p==0) {
cnt++;
now /= p;
}
else break;
}
if(cnt>0) tmp.put(p, cnt);
}
for(int key : tmp.keySet()){
if(map.containsKey(key)){
int mv = map.get(key), tv = tmp.get(key);
if(mv < tv) map.replace(key, mv, tv);
}else{
map.put(key, tmp.get(key));
}
}
}
// 최소로 필요한 소인수들을 곱해 최소공배수 구하기
int answer = 1;
for(int key : map.keySet()) answer *= Math.pow(key, map.get(key));
return answer;
}
}