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 |