[알고리즘/프로그래머스] 12940. 최대공약수와 최소공배수

문제

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

최대공약수와 최소공배수

문제 설명

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

제한 사항

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

백준이었나 do it 알고리즘 책인가 기억이 잘 안나는데 예전에 최소공배수 최대공배수 관련해서 엄청 간단하게 푼 기억이 있어서 찾아보니 유클리드 호제법인 걸 알게 되었다.

해당 포스팅에서 아래 표만 보고(사실 이게 다지만,,,,) 구현하긴 했지만 이걸 기억해내는 게 더 중요한 것 같다.

사람이 참 신기한 게 그때 풀면서도 오~~하면서 풀었으면서 지금은 어떻게 풀었는지 기억이 나지 않는다.. 이래서 반복이 중요성한가보다

class Solution {
    public int[] solution(int n, int m) {

        int gcd = gcd(n, m);
        int lcm = (n * m) / gcd;
        
        int[] answer = {gcd, lcm};
        return answer;
    }

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