[Java] 프로그래머스 - level1 - 최대공약수, 최소공배수

문제 설명

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

제한사항

• 두 수는 1이상 1000000이하의 자연수입니다.

 

static public int[] solution(int n, int m) {
        
    int[] answer = {gcd(n,m), lcm(n,m)};

    return answer;
}

//최대공약수 Greatest Common Divisor, 시간 복잡도 : O(logN)
static int gcd(int a, int b) {
     while(b!=0) {
         int r=a%b;
         a=b;
         b=r;
     }
     return a;
 }

//최소공배수 Least Common Multiple
 static int lcm(int a,int b) {
     return a*b/gcd(a,b);
 }

 //무차별 대입, 시간 복잡도 : O(n)
public static int gcd2(int a, int b) {
    int answer = 0;
    for(int i = 1; i <= b; i++) {
        if(a % i == 0 && b % i == 0) answer = i;
    }
    return answer;
}

 

처음에는 무차별 대입으로 시도해봤으나, 더 나은 알고리즘 방법을 알게되어서 사용해보았다.

 

최대공약수 - 유클리드 호제법

• a를 b로 나눈 나머지를 r이라고 할때 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다는 성질을 이용한다.