Programmers - N개의 최소공배수 with JAVA (V)

 

 

 

문제

배열로 숫자 리스트가 주어질 떄, 모든 수의 최소 공배수를 구하라.

 

 

로직

- 두 수의 최대 공약수를 구한다.

- 두 수의 최소 공배수 = AxB/최대공약수

- 반복

 

- 또는 아래 다른 공식 활용 a%b==c 일때, b%c가 0이될때까지 반복하는 방식

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        Arrays.sort(arr);
        int length = arr.length;
        int now_value = arr[length-1];
        for(int i=length-2; i>=0; i--){
            int value = arr[i];
            while(true){
                if(now_value % value == 0 && arr[i] % value == 0){
                    break;
                }
                value --;
            }
            now_value = arr[i]*now_value/value;
        }
        return now_value;
    }
}

 

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        int start = 1;
        for(int i=0; i<arr.length; i++){
            int now = find(start, arr[i]);
            start = (start*arr[i])/now;
        }
        return start;
    }
    public static int find(int a, int b){
        List<Integer> resultA = new ArrayList<>();
        List<Integer> resultB = new ArrayList<>();
        for(int i=1; i<=(int)Math.sqrt(a); i++){
            if(a % i == 0){
                resultA.add(i);
                resultA.add(a/i);
            }
        }
        for(int i=1; i<=(int)Math.sqrt(b); i++){
            if(b % i == 0){
                resultB.add(i);
                resultB.add(b/i);
            }
        }
        int answer = 1;
        for(int nowA : resultA){
            for(int nowB : resultB){
                if(nowA == nowB){
                    answer = Math.max(nowA, answer);
                }
            }
        }
        return answer;
    }
}

 

 

다른 방법

예를들어, 14, 8의 최대공약수 구하기

14%8 == 6

8%6 == 2

6%2 == 0

이러한 경우 두 수의 최대 공약수는 2가 된다.

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        Arrays.sort(arr);
        int length = arr.length;
        int now_value = arr[length-1];
        for(int i=length-2; i>=0; i--){
            int value1 = now_value;
            int value2 = arr[i];
            while(true){
                int spare = value1 % value2;
                if(spare == 0){
                    now_value = arr[i] * now_value / value2;
                    break;
                }
                value1 = value2;
                value2 = spare;
            }
        }
        return now_value;
    }
}