코딩 테스트

[java] 최대공약수와 최소공배수

S_N_Y 2024. 3. 8. 09:31

 

1️⃣문제 : 

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.

배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

 

2️⃣제한 사항 : 

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

 

3️⃣개인 정답 및 해설 : 

class Solution {
    public int[] solution(int n, int m) {
        int max = Math.max(n, m); //a
        int min = Math.min(n, m); //b
        
        // 최대 공약수
        while(min != 0) {
            int r = max % min;
            gcd = min;
            min = r;
        }
        
        // 최소 공배수 = 두 수의 곱 / 최대공약수
        int lcm = n * m / max;
        int[] answer = {max, lcm}; // 최대공약수, 최대공배수
        return answer;
    }
}

Math함수를 이용해서 입력받은 두 수 중에 큰 수를 max 변수에 담고 똑같이 입력받은 두 수 중에 작은 수를 min변수에 담았다. 그 다음 유클리드 호제법을 이용하여 최대공약수를 구하는 반복문을 만들어주었는데 여기서 유클리드 호제법이란 두 수의 최대공약수를 구하는 알고리즘으로 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 최소공배수는 위의 주석과 같이 구해주면 나온다.

 

✴️사용한 개념 정리 : 

1) 유클리드 호제법 : 두 수의 최대공약수를 구하는 알고리즘 - 방법은 위의 설명 참조

 

 

'코딩 테스트' 카테고리의 다른 글

[java] 제일 작은 수 제거하기  (0) 2024.03.06
[java] 중복된 숫자 개수  (0) 2024.02.26
[java] 피자 나눠먹기(3) - Math.ceil  (0) 2024.02.18
[java] 편지  (0) 2024.02.11
[java] 배열 뒤집기 - collections.reverse  (0) 2024.02.09