아찌방 하우스

문제

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

제한사항

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

입출력 예

코드

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        Arrays.sort(arr);
        int lcm = arr[arr.length - 1]; // 초기값을 배열의 최댓값으로 설정
        
        for (int i = 0; i < arr.length - 1; i++) {
            lcm = findLCM(lcm, arr[i]);
        }

        return lcm;
    }

    // 최대 공약수를 구하는 메서드
    private int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 최소 공배수를 구하는 메서드
    private int findLCM(int a, int b) {
        return a * b / findGCD(a, b);
    }
}

풀이

처음에

"N개의 숫자 중 가장 큰 값의 배수 중

모든 숫자들로 나눴을 때의 나머지 값이 0이면 최소 공배수가 된다"

라는 생각으로 문제를 풀었습니다.

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        Arrays.sort(arr);
        int max = arr[arr.length-1];
        int tmp = max;
        int i = 1;
        while(true){
            int cnt = 0;
            for(int n : arr){
                if(tmp%n == 0) cnt++;
                else break;
            }
            if(cnt == arr.length){
                answer = tmp;
                break;
            }
            tmp = max*(++i);
        }
        return answer;
    }
}

잘 풀리긴 하는데

이전에 유클리드 호제법 을 사용해서

최대 공약수, 최소 공배수를 구하는 것을 이용할 수 있겠다 싶어서

해본게 맨 처음에 코드입니다.

시간이 비슷할 거라고 생각했는데

유클리드 호제법을 사용하는게 더 빠르더라고요.

재밌길래 기록해두려고 가져와 봤습니다.

문제

첫 번째 분수의 분자와 분모를 뜻하는 denum1, num1, 두 번째 분수의 분자와 분모를 뜻하는 denum2, num2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

제한사항

• 0 <denum1, num1, denum2, num2 < 1,000

입출력 예

코드

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int[] answer = new int[2];
        int denum = (denum1*num2)+(denum2*num1);
        int num = num1*num2;
        int n = gcd(denum, num);
        answer[0] = denum/n;
        answer[1] = num/n;
        return answer;
    }
    public static int gcd(int num1, int num2)
    {
        if(num1%num2 == 0)
        {
            return num2;
        }
        return gcd(num2, num1%num2);
    }
        
}

해설

결과를 기약 분수의 형태로 나타내야 한다.

즉

이렇게 결과 값이 나와야 한다.

1단계를 구한 후

2단계에서 GCD로 나누면 

3단계 결과가 나온다.

GCD를 구하는 방법은 유클리드 호제법을 활용했다.

이에 대해서는 

https://fall-in-dream.tistory.com/11

여길 참고해주세요.

최대 공약수와 최대 공배수의 개념

1) 공약수

두 정수의 공통 약수를 공약수라고 한다.
두 정수 a, b에 대하여 e가 a의 약수이면서 b의 약수일 때 e를 a, b의 공약수라고 한다.

2) 최대공약수

두 정수의 공약수 중 가장 큰 것을 최대공약수라고 한다.
또한 최대공약수는 다음의 성질을 만족한다.
a, b의 최대공약수가 g이다. ⇔ a = ga′, b = gb′이면 a′, b′는 서로소이다.

3) 공배수

두 정수의 공통 배수를 공배수라고 한다.
두 정수 a, b에 대하여 c가 a의 배수이면서 b의 배수일 때 c를 a, b의 공배수라고 한다.

4) 최소공배수

양의 공배수 중 가장 작은 것을 최소공배수라고 한다.

코드

내가 이것을 보고 생각했을 때 짠 코드이다.

class Solution
{
	public static void main(String args[]) throws Exception
	{
		int num1 = 1250;
		int num2 = 80;
        	int g = gcd(num1, num2, num2);
        	int l = (num1*num2)/g;
		System.out.println("1250과 80의 GCD : "+g);
		System.out.println("1250과 80의 LCM : "+l);
	}
    public static int gcd(int num1, int num2, int n)
    {
        if(num1%n == 0 && num2%n == 0)
        {
            return n;
        }
        return gcd(num1, num2, n-1);
    }
}

유클리드 호제법

여기서  Q = A/B(A를 B로 나눈 몫), R = A%B (나머지) 이다.

예시

 1250과 580의 최대공약수를 구하라.

• A = B X Q + R
• 1250 = 580 X 2 + 90
• 580 = 90 X 6 + 40
• 90 = 40 X 2 + 10
• 40 = 10 X 4

4번째에서 R = 0 가 되니까, 직전의 R 인 10이 1250과 580의 최대공약수가 됩니다.

코드

class Solution
{
	public static void main(String args[]) throws Exception
	{
		int num1 = 1250;
		int num2 = 80;
        	int g = gcd(num1, num2);
        	int l = (num1*num2)/g;
		System.out.println("1250과 80의 GCD : "+g);
		System.out.println("1250과 80의 LCM : "+l);
	}
    public static int gcd(int num1, int num2)
    {
        if(num1%num2 == 0)
        {
            return num2;
        }
        return gcd(num2, num1%num2);
    }
}