[Lv2] N개의 최소공배수

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

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

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

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

 

---

 

여러 개의 수의 최소공배수를 구하는 문제입니다.

 

중학 수학 때 최소공배수와 최대공약수의 정의를 공부할 때, 보통 2개에 대해서는 많이 해봤을테고, 좀 꼬아도 3개 정도였던 기억이 납니다.

 

2개에 대해서는 이미 풀어본 바 있습니다.

[Coding Quiz/programmers] - [Lv1] 최대공약수와 최소공배수

 

최소공배수를 구하는 방법은 몫이 서로소가 될 때까지 나눈 수들의 곱으로 구하는 법과,

소인수분해 결과를 합쳐보는 방식이 있는데,

 

전자는 수들이 많아질 수록 서로소를 판단하기 까다로워질 것 같으니, 소인수분해로 갑니다.

 

60, 37, 24의 최소공배수를 구해봅시다.

 

60 = (2^2)*(3)*(5),

37 = 37,

24 = (2^3)*(3) 입니다.

 

최소공배수는 (2^3)*3*5*37 = 4440입니다.

 

소인수분해 결과로 나온 소수는 모두 포함하면서, 결과 중 승이 높은 승을 따릅니다. 3과 5와 37은 1승으로 들어간 거죠.

 

 

풀이 전략은 이렇습니다.

 

우선 모든 수는 소인수분해가 가능합니다.

 

어떤 소수들로 이루어지느냐? 주어진 수 중 가장 큰 수 이하의 소수들로 구해집니다.

 

위에서는 60이하의 소수. 즉, 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59의 n승의 곱으로 각각 표현이 되겠네요.

 

소수들의 집합들을 구하는 건 이전에 소수 문제에서 다뤘습니다.

[Coding Quiz/programmers] - [Lv1] 소수의 합, 소수 찾기

Arrays.sort(arr);
int primecal = (int)(Math.sqrt(arr[arr.length-1]));
boolean[] check = new boolean[arr[arr.length-1]];
check[0] = true;
for(int i=2;i<=primecal;i++) {
    for(int j=i*2;j<=arr[arr.length-1];j+=i) {
        if(j-1<check.length) {
            check[j-1] = true;
        }
    }
}
int primecount = 0;
for(int i=1;i<check.length;i++) {
    if(check[i]==false) primecount++;
}
int[] primes = new int[primecount];
int[] maxcounts = new int[primecount];
int index = 0;
for(int i=1;i<check.length;i++) {
    if(index>primes.length-1) break;
    if(check[i]==false) {
        primes[index++] = i+1;
    }
}

primecount로 소수의 수를 세어, 그만한 크기의 primes라는 배열에 각각 소수를 넣습니다.

 

위의 예시라면, 17개의 칸에 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59가 각각 들어가겠죠.

 

maxcounts는 위의 풀이에서 설명했듯 승의 최대치를 저장하기 위해 만든 김에 같은 크기로 함께 만들어 둔 것.

 

for(int i=0;i<arr.length;i++) {
    int now = arr[i];
    int[] counts = new int[primecount];
    while(now>1) {
        for(int j=0;j<primes.length;j++) {
            if(now%primes[j]==0) {
                now/=primes[j];
                counts[j]++;
            }
        }
    }
    for(int j=0;j<counts.length;j++) {
        if(counts[j]>maxcounts[j]) maxcounts[j]=counts[j];
    }
}

수 마다 count라는 배열을 만들어준 후,

 

값이 1이 될 때 까지 나누면서 해당 소수를 얼마나 썼는지 1씩 더하면서 기록합니다.

 

그리고 maxcounts와 비교하여 최대값을 maxcounts에 기록합니다.

 

int sum = 1;
for(int i=0;i<primes.length;i++) {
    int tmp = 1;
    for(int j=1;j<=maxcounts[i];j++) {
        tmp *= primes[i];
    }
    if(tmp>1) sum*=tmp;
}
return sum;

이제 해당소수(primes[i])의 승(maxcounts) 만큼 곱해줍니다. Math.pow를 하시든..

 

그리고 반환하면 끝.