프로그래머스 - 최대공약수와 최소공배수 Java (+ 유클리드 호제법)

문제 설명

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

제한 사항

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

 

class Solution {
    int gcd(int n, int m){
        if(m==0) return n;
        else return gcd(m , n%m);
    }
    
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        if(n<m){
            int tmp = n;
            n = m;
            m = tmp;
        }
        
        answer[0] = gcd(n, m);
        answer[1] = n*m / answer[0]; 
            
        return answer;
    }
}

 

유클리드 호제법을 사용해 풀이.

 

유클리드 호제법 Euclidean Algorithm

→ 두 개의 자연수가 주어졌을 때 두 수의 최대 공약수를 구하는 알고리즘이다.

 

두 자연수 A, B와 ( A < B ) A를 B로 나눈 나머지 C가 있을 때 A와 B의 최대공약수는 B와 C의 최대공약수와 같다. (수학 증명)

이 증명을 사용해서 B를 나머지 C로 나누고 C를 둘 사이의 나머지로 또 나누는 것을 반복하다 나머지가 0이 된다면 그 나눈 수가 A와 B 사이의 최대 공약수가 된다. 

 

예시 1 ) 두 자연수가 3과 12 일 때

1. 큰 수를 작은 수로 나눈 나머지 구하기 → 12/3 = 4 ... 0
2. 나머지가 0이기에 나누는 수인 3이 최대 공약수가 된다.

 

 예시 2 ) 두 자연수가 2와 5일 때

1. 큰 수를 작은 수로 나눈 나머지 구하기 → 5/2 = 2 ...1
2. 나머지가 0이 아니기에 2를 다시 나머지 1로 나누기 → 2/1 = 2 ... 0
3. 나머지가 0이기에 나누는 수인 1이 최대 공약수가 된다.

 

int gcd(int n, int m){
        if(m==0) return n;
        else return gcd(m , n%m);
    }

 

※ GCD : Greatest Common Divisor = 최대 공약수

 

이를 코드로 구현하면 위와 같다. 나머지가 0이 될 때 까지 재귀 함수를 돌게된다.

첫번째 파라미터 N이 나누어지는 수, 두번째 파라미터 M이 나누는 수이자 전 재귀함수로 인한 나눗셈의 나머지 값이 들어가기에 M이 0이라면 나머지가 0인 것이므로 n을 반환하고 끝나게 된다. M이 0이 아니라면 다시 재귀함수를 돈다.

 

최대공배수는 두 수의 곱을 최대 공약수로 나눈 값이므로 유클리드 호제법으로 구한 최대공약수를 활용해 풀이.

 

  

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

프로그래머스