[프로그래머스 Lv.1] 최대공약수와 최소공배수 java

문제설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.

배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

제한조건

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

 

입출력 예

n	m	return
3	12	[3,12]
2	5	[1,10]

 

Solution

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int big = Math.max(n, m);
        int small = Math.min(n, m);
        int gcd = 0;
        int lcm = 0;
        //최대공약수
        while(big%small>0) {
        	int tmp = big%small;
        	big = small;
        	small = tmp;
        }
        gcd = small;
        
        //최소공배수
        lcm = (n*m)/gcd;
        
        answer[0] = gcd;
        answer[1] = lcm;
        
        return answer;
    }
}

최대공약수 구하기 = 유클리드 호제법 !
1. 뺄셈 방식 : 큰 수에서 작은 수를 계속해서 빼나가다 결과값이 0이 나오게 하는 수가 최대 공약수.
2. 나눗셈 방식 : 큰 수에서 작은수 를 나누어 나머지가 0일때 작은 수가 최대 공약수.
 * 나머지가 0이 아니면 큰 수  = 작은 수 , 작은 수 = 나머지 값을 넣어 나누기를 반복

** 뺄셈 방식보다 나눗셈 방식이 더 효율성이 좋다.

최소공배수 구하기 = 두 수를 곱한 후 최대공약수로 나누어준다.

 

 

다른사람풀이

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);
   }

    public static void main(String[] args) {
        TryHelloWorld c = new TryHelloWorld();
        System.out.println(Arrays.toString(c.gcdlcm(3, 12)));
    }
}

최대공약수를 재귀함수를 사용하여 더 깔끔하게 구현하였다.