프로그래머스 N개의 최소공배수 (JAVA)

프로그래머스 N개의 최소공배수를 구하는 문제이다.

 

여기서는 기존의 2개 숫자를 주고 최대공약수를 구한 이후 a*b / 최대공약수 를 하는 방식을 여러번 반복하는 것으로 알고리즘을 만들었다.

 

최대공약수를 만드는 공식은 유클리드 호제법을 사용한다.

 

gcd(a, b) 를 하고 다시 return 값으로 gcd(b, a%b) 가 들어가게 된다.

 

처음에  생각하기로는 a와 b 사이에 크기 비교가 들어가야한다고 생각했다. 무조건 뒤에오는 숫자가 작아야 한다고 생각했기 때문이다.

 

하지만 크기는 중요하지 않았다.

 

왜냐하면 gcd(24, 9) 와 gcd(9, 24)의 값은 똑같이 나오기 때문이다.

예를 들어 gcd(24, 9) 로 시작하게 되면 두번째 재귀로 불러오는 것은 gcd(9, 3) 세번째 재귀는 이루어지지 않는다 이때 a%b가 0이 되면서 리턴값으로 뒤에있는 값을 리턴해주기 때문이다.

 

그럼 gcd(9, 24) 를 해보자. 두번째로 나오는 것은 gcd(24, 9)이다. 앞 예시의 가장 첫부분과 똑같아지지 않는가?...

그럼으로 알아서 정렬이 된다.

 

위 방법을 통해 구현한 코드이다.

answer, answer2 로 나눈 이유는 최대공약수와 최소공배수가 무엇인지 구별하기 위해 이렇게 만들었다. 아래 더 효율적으로 만든 코드또한 첨부한다.

 

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        int answer = 0; //최대공약수
        int answer2 = 0; //최소공배수
        //길이가 1이면 그게 그냥 답이다.
        if(arr.length==1){
            answer2 = arr[0];
        }
        Arrays.sort(arr);
        //일단 2보다 크면 최대공약수를 찾음
        if(arr.length >= 2){
            answer = gcd(arr[0], arr[1]);
            answer2 = (arr[0]*arr[1]) / answer;
        }
        for(int i =2 ;i<arr.length; i++){
            answer = gcd(answer2, arr[i]);
            answer2 = answer2*arr[i] / answer;
        }
        //여기까지해서 answer 에 최대공약수를 넣음.
        
        //모든 배열을 곱한뒤 최대공약수로 나눠서 정답에 넣는다.
        return answer2;
    }
    
    private static int gcd(int a, int b){
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        int rest = max%min;
        if(rest == 0){
            return min;
        }else{
            return gcd(rest, min);
        }
    }
}

 

 

위 코드가 아직 지저분한 코드이고 gcd 즉 최대공약수를 구할때도 크기를 비교하고 있다. 하지만 우리는 크기가 중요하지 않다는 것을 알았으니 이부분도 제거하겠다.

 

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        // 배열이 1개일 경우 바로 반환
        if (arr.length == 1) {
            return arr[0];
        }
        
        // 첫 번째 두 요소의 최소공배수를 먼저 구함
        int answer = lcm(arr[0], arr[1]);

        // 배열의 나머지 요소들과 최소공배수를 계산
        for (int i = 2; i < arr.length; i++) {
            answer = lcm(answer, arr[i]);
        }

        return answer;
    }

    // 최소공배수(LCM) 구하는 함수
    private static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);  // LCM = (a * b) / GCD
    }

    // 최대공약수(GCD) 구하는 함수 (유클리드 호제법)
    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}