[프로그래머스/Programmers] 최대공약수와 최소공배수 (Java - 수학)

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

프로그래머스

---

⭐️ 코드

public int[] solution(int n, int m) {
    // answer[0]=최대공약수, answer[1]=최소공배수
    int[] answer = new int[2]; 
    
    int max = Math.max(n, m);
    int min = Math.min(n, m);
    
    answer[0] = gcd(max, min); // 최대공약수
    answer[1] = max*min/answer[0]; // 최소공배수
    
    return answer;
}

// 최대공약수를 구하기 위한 재귀함수
public int gcd(int a, int b) {
    if(a%b == 0) {
        return b;
    }
    return gcd(b, a%b);
}

 

---

💡 문제 풀이

최대공약수와 최소공배수 문제는 수학을 알아야 하는 문제다.

기본적으로 최대공약수와 최소공배수를 찾는 계산식을 알아야 풀기가 편하다.

 

아래 식은 유클리드 호제법 (Euclidean Algorithm)을 사용한 최대공약수를 찾는 재귀함수이다.

// 최대공약수
// answer[0] = gcd(max, min);
public int gcd(int a, int b) {
    if(a%b == 0) {
        return b;
    }
    return gcd(b, a%b);
}

간단히 설명하자면 두 수 중에서 가장 큰 수를 작은 수로 계속 반복해서 나눠서 나머지가 0이 될 때까지 만드는 방법이다. 그렇게 출력되는 수는 두 숫자의 최대공약수가 된다. 

 

유클리드 호제법은 아래 포스팅에서 잘 설명해주니 읽어보자!

 

유클리드 호제법(Euclidean-algorithm)

 

// 최소공배수
answer[1] = max * min / answer[0];

최소공배수는 두 수를 곱하여 최대공약수로 나눠주면 쉽게 찾을 수 있다!!

---

👀 후기

최대공약수와 최소공배수를 찾는 수학적 공식을 바로바로 생각하기가 어렵다... 그동안 너무 수학을 하지 않았...😂

처음 풀때는 그냥 막 풀었는데 두 번째 풀 때는 유클리드 호재법과 최소공배수를 구하는 방식에 대해 제대로 알게 된 것 같다.

항상 생각하고 더 열심히 찾아보며 풀어보자!