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

 

 

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

 

 

나의 접근.

최대공약수를 구하는 방법은 0부터 주어진 두 수 중 작은 수까지 반복하여, 나눌때 나머지가 0인 수를 구한다.

그 수들의 곱이 최대공약수이다.

최소공배수를 구하는 방법은 최대공약수에 최종적으로 나온 나머지 값을 값을 곱하면 최소공배수이다.

 

class Solution {
    public int[] solution(int n, int m) {
        int a = 1; // 최대 공약수
        int b = 1; // 최소 공배수
        // 작은 수 구하기
        int min = n < m ? n : m;
        
        // 최대공약수 구하기
        for(int i = 2; i <= min ; i++){
            if( n % i == 0 && m % i == 0){
                a *= i;
                n = n / i;
                m = m / i;
                i--;
            }
        }
        
        // 최소공배수 구하기
        b = a * n * m;

        int[] answer = {a ,b};

        return answer;
    }
}

// 입력값
n : 3
m : 12

// 결과
[3, 12]

 

 

 

링크.

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