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

프로그래머스

 

 

 

이해하기

기본 중의 기본인 최대공약수와 최대공배수.. 왠지 기억이 안 나서 구현을 제대로 하지 못했다.

이번 기회에 제대로 정리해둬야지...!

 

최대공약수를 구하는 알고리즘 중 하나인 유클리드 호제법을 사용하였다.

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

처음에 식만 보고는 감이 잘 안 잡혔는데 예시를 보니 이해가 됐다.

 

e.g. 1071과 1029의 최대공약수

• 1071은 1029로 나누어 떨이지지 않기 때문에 1071을 1029로 나눈 나머지를 구함 = 42
• 1029는 42로 나누어 떨어지지 않기 때문에 1029를 42로 나눈 나머지를 구함 = 21
• 42는 21로 나누어 떨어짐 = 42 % 21 = 0
• 이 때 21이 최대공약수

최소공배수는 최대공약수를 활용해서 구할 수 있다.

 

최소공배수 = n * m / 최대공약수

 

e.g. 36과 24의 최소공배수

• 둘의 최대공약수 = 12
• 36 * 24 = 864
• 864 / 12 = 72
• 이 때 72가 최소공배수

 

문제풀이

class Solution {
    public int[] solution(int n, int m) {
        int a = Math.max(n, m);
        int b = Math.min(n, m);
        
        int[] answer = new int[2];
        
        answer[0] = gcd(a, b);
        answer[1] = n * m / answer[0];
        
        System.out.println(answer[0] + " " + answer[1]);
        
        return answer;
    }
    
    public int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
}

 

        int a = Math.max(n, m);
        int b = Math.min(n, m);

 

n과 m 중 큰 수를 a, 작은 수를 b로 잡는다.

 

        int[] answer = new int[2];
        
        answer[0] = gcd(a, b);
        answer[1] = n * m / answer[0];

 

answer[0]에 최대공약수, answer[1]에 최소공배수를 담는다.

이 때 gcd 함수를 살펴보자.

 

    public int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

 

위에서 설명한 유클리드 호제법을 재귀식으로 나타낸 것이다.

 

e.g. 1071과 1029의 최대공약수

• a = 1071, b = 1029
• a = 1029, b = 42
• a = 42, b = 21
• a = 21, b = 0
• 이 때 a의 값이 최대공약수

이런 로직으로 재귀가 돌아가려면 b가 0일 때 a값을 리턴하도록 하는 조건문이 들어가야하고, b가 아직 0이 아니라면 다시 gcd()를 돌리는데, 이 때 a자리에 b값을, b자리에 a % b 값을 넣어준다.

 

 

 

 

---

 

[프로그래머스] 최대공약수와 최소공배수-JAVA