[Java] 프로그래머스_12940 : 최대공약수와 최소공배수

유클리드 호제법

최대공약수와 최소공배수 : Level1

 

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

프로그래머스

 

 

 

처음 작성한 코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int [2];
        int cnt = 2;
        int min = 1;
        int max = 1;
        int tmp = 0;
        
        if (n > m) {
            tmp = n;
            n = m;
            m = tmp;
        }
        
        while (cnt <= m) {
            if (n % cnt == 0 && m % cnt == 0) {
                max *= cnt;
                n /= cnt;
                m /= cnt;
            } else {
                cnt++;
            }
        }
        answer[0] = max;
        answer[1] = answer[0] * n * m;
        
        
        return answer;
    }
}

 

 

두 번째 작성한 코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        // 최대 공약수를 구하는 함수 호출
        int gcd = getGCD(n, m);
        
        // 최소 공배수 계산
        int lcm = n * m / gcd;
        
        // 결과값 배열에 저장
        answer[0] = gcd;
        answer[1] = lcm;
        
        return answer;
    }
    
    // 최대 공약수를 구하는 함수
    private int getGCD(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

 

 

 

여기서 사용된 알고리즘은 "유클리드 호제법"이다.

유클리드 호제법은 두 수의 최대공약수를 구하는 간단하면서도 효율적인 방법 중 하나이다.

while (b != 0) : b가 0이 아닌 동안 반복한다.

int r = a % b; : 현재 a를 b로 나눈 나머지를 구한다.

a = b; : a에는 기존의 b 값을, 
b = r; : b에는 나머지를 대입한다. 이 과정을 반복하면서 두 수의 최대공약수를 찾는다.

최종적으로 return a; : 최대공약수를 반환한다.

 

예를 들어, a가 48, b가 18인 경우

처음에는 a = 48, b = 18이다.

나머지를 구하면 r = 12가 되고, a = 18, b = 12로 갱신된다.
다시 나머지를 구하면 r = 6이 되고, a = 12, b = 6으로 갱신된다.
한 번 더 나머지를 구하면 r = 0이 되고, a = 6, b = 0으로 갱신된다.

b가 0이 되면 반복이 종료되고, 최대공약수는 a = 6이 된다.

 

 

또한, 아래 공식을 이용하여 최소공배수를 구했다.

최소공배수 = num1 * num2 / 최대공약수

 

 

 

문제점 : 최대공약수, 최소공배수 관련 수학 공식을 잊고 있었고, "유클리드 호제법"이라는 알고리즘을 몰랐다.

해결 : 관련 공식을 검색하여 찾고 코드 작성 시 메서드화 시켜서 작성하였다.

깨달은 바 : 수학 공식이 있다면 공식을 활용하고, 코드의 가독성을 위해 깔끔한 코드를 작성하도록 하자.