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

본 문제를 풀기 위해서는 유클리드 호제법이라는 알고리즘에 대해 알아야 한다. 컴퓨터 관련 학생이라면 고등학교 때나, 대학교에서 본 기억이 있을 거다. 유클리드 호제법을 통해서 최대공약수(Greatest Common Division(GCD))를 빠르게 계산할 수 있고, 그것을 토대로 최소공배수(Least Common Multiple(LCM)) 또한 구할 수 있다.

 

이 알고리즘은 다음과 같은 수식으로 나타낼 수 있다.

 

GCD(A, B)

IF A%B = 0, THEN GCD = B

ELSE GCD(B, A%B)

 

보시다시피 이 알고리즘을 표현하려면 재귀함수로 나타내야한다. 추가적으로 이 알고리즘의 시간복잡도는 O(log N)이다.

 

class Solution {
    public int[] solution(int n, int m) {
        //최대공약수와 최소공배수, 두 숫자를 넣어야 하기 때문에 answer 길이를 지정
        int[] answer = new int[2];
        //n과 m 중에 큰 숫자와 작은 숫자를 지정
        int bNum = Math.max(n, m);
        int sNum = Math.min(n, m);
        //최대공약수 계산
        int gcd = gcdA(bNum, sNum);
        answer[0] = gcd;
        //최소공배수는 두 정수의 곱해서 최대공약수를 나누면 나온다
        answer[1] = bNum * sNum / gcd;
        
        return answer;
    }
    
    //유클리드 호제법의 식
    public static int gcdA(int n, int m) {
        if(n % m == 0) {
            return m;
        }
        return gcdA(m, n%m);
    }
}

 

재귀함수란 gcdA의 function과 같이 n%m이 정확히 나눠지기까지 계속 function을 실행시켜주는 것을 말한다.

 

문제출저:

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