[알고리즘] 최대공약수와 최소공배수 구하기

문제 요구사항

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항
두 수는 1이상 1000000이하의 자연수입니다.

풀이

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = {};
        int max; //최대공약수
        int min; //최소공배수
        max = getMax(n,m);
        min = getMin(n,m);
        answer = new int[] {max,min};
        return answer;
    }
    private int getMax(int n, int m){
        int gcd=1;
        for(int i = 2;i<=Math.min(n,m);i++){
            if(n % i == 0 && m % i == 0)
                gcd = i;
        }
        return gcd;
    }
    private int getMin(int n, int m){
        return n * m / getMax(n,m); //두 수의 곱 = 최대공약수 * 최소공배수
    }
}

 

모범답안

import java.util.Arrays;

class TryHelloWorld {
      public int[] gcdlcm(int a, int b) {
        int[] answer = new int[2]; //정답: 두 자리의 정수 배열 선언

          answer[0] = gcd(a,b); //최대공약수는 함수로 구하기
        answer[1] = (a*b)/answer[0]; //최소공배수 = 두 수의 곱 / 최대공약수 공식
        return answer;
    }

   public static int gcd(int p, int q)
   {
    if (q == 0) return p;
    return gcd(q, p%q); //재귀함수 -> 이런 방법도 있구나 정도만 이해
   }

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        for (int i = 1; i < n + m; i++) {
            if (n % i == 0 && m % i == 0) {
                answer[0] = i;
                answer[1] = n * m / answer[0];
            }
        }
        return answer;
    }

}

import java.util.Arrays;

class TryHelloWorld {
    public int[] gcdlcm(int a, int b) {
        int[] answer = new int[2];
        int mini = 0;
        int maxi = 1;

        for(int i = 1; i<=a; i++) //2부터 시작해도 됨
                    if(a%i==0&&b%i==0)
                        maxi = i; 

                for(int i = a*b; i>0; i--)
                    if(i%a==0&&i%b==0)
                        mini = i;

        answer[0] = maxi;
        answer[1] = mini;

        return answer;
    }

잘한 점

함수적 접근은 좋음

인사이트

최소공배수 * 최대공약수 = 두 수의 곱
최대공약수는 재귀함수 호출로 푸는 방법도 있다
하지만, O(n)으로 직관적으로 푸는 법도 가능하다.

Github 링크

https://github.com/ginsengcandy/Coding-Test-Practice/commit/c852901cec24be3f701345cb8c25bbbf9d4d29c7

[level 1] Title: 최대공약수와 최소공배수, Time: 0.18 ms, Memory: 83.1 MB -Baekjo… · ginsengcandy/Coding-Test-Pract

 

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/12940#