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

프로그래머스 12940번 - 최대공약수와 최소공배수

프로그래머스 12940번 - https://programmers.co.kr/learn/courses/30/lessons/12940

 

요구사항

1. 두 수의 최대공약수와 최소공배수를 배열에 담아서 반환하라.

 

요구사항 분석 및  풀이과정

1. 최대공약수는 재귀 또는 반복으로 구할 수 있으나 BigInteger 클래스에 이미 구현되어있으므로 사용하는 것도 좋다.

2. 최소공배수는 최대공약수로 다음과 같이 표현 가능하다.

 

lcd(m, n) = m * (n / gcd(m, n)) ( gcd : 최대공약수, lcd: 최소공배수 )

 

m * n을 곱하고 나누지 않는 이유는 m과 n의 크기에 따라 오버 플로우가 발생할 수 있기 때문이다. 미리 나눈 후 곱할 경우 오버 플로우가 발생하지 않는다.

 

소스코드 작성

import java.math.BigInteger;

class Solution {
    
    private static int gcd(int n, int m) {
        return BigInteger.valueOf(n).gcd(BigInteger.valueOf(m)).intValue();
    }
    
    private static int lcd(int n, int m) {
        return n * (m / gcd(n, m));
    }
    
    public int[] solution(int n, int m) {
        return new int[]{ gcd(n, m), lcd(n, m) };
    }
}

 

결과

 

소스코드 깃허브 주소

링크