[프로그래머스|JAVA] N개의 최소공배수 | gcd(), lcm()

[문제 링크]

프로그래머스

---

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        int answer = 1;
        int num = 2;
        
        Arrays.sort(arr);
        int max = arr[arr.length -1];
        
        if(max == 1) return max;
        while (max >= num) {
            boolean bool = false;
            
            for(int i = 0; i < arr.length; i++){
                if(arr[i]%num == 0){
                    arr[i] = arr[i]/num;
                    bool = true;
                }
            }
            if(bool) answer *= num;
            else num++;
        }
        
        for(int i = 0; i < arr.length; i++){
            answer *= arr[i];
        }
        return answer;
    }
}

[접근법]

1. arr 배열을 정렬하여 가장 큰 값을 max로 지정한다.
2. max의 값이 1이면 모든 값이 1이므로 max를 반환한다.
3. 그 외의 수는 소인수를 구하는 방식을 이용하여 나머지가 0인 값을 구하고 몫으로 배열의 값을 업데이트한다
4. 이후 나머지가 0이 되는 num 값을 answer에 곱한다. 
   • 이때, bool 값을 사용하여 모두 나머지가 0인 값이 없을 때, num 값을 ++하기 위함이다.
5. max 값까지 반복한 후, 업데이트한 값의 arr 배열의 값들을 answer에 곱한다. 

 

---

 

최소 공배수를 구하는 방법은 여러가지 있으나, 

가장 기본적인 방법인 공약수와 서로소를 곱하는 방법을 사용했다.

 

bool을 사용하는 방법을 생각하지 못했다면

코드가 지저분하고 효율성이 떨어졌을 것 같다.

 

하지만, 최대 공약수를 구하는 gcd()라는 함수와 

gcd() 함수를 이용하여 최소 공배수를 구하는 lcm() 함수를 사용했으면

훨씬 간단하고, 빠르게 구현했을 것 같다.