최대공약수와 최소공배수
💡 문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.
배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.
예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
💡 제한 조건
- 두 수는 1이상 1000000이하의 자연수입니다.
🔑 입출력 예
| n | m | return |
|---|---|---|
| 3 | 12 | [3, 12] |
| 2 | 5 | [1, 10] |
💻 작성 코드 - java
[ 유클리드 호제법 ]
- 두수 A,B 의 최대공약수 G ( gcd(a , b) ), 최소공배수 L ( lcm(a , b) ) 이면
AB = LG- A를 B로 나눈 몫을 Q 라하고, 나머지를 R 라고 할 때,
gcd(A , B) = gcd(B , R)(여기서 A ≥ B이고, 0 ≤ R ≤ B)- 위의 과정을 계속 반복해, 어느 한쪽이 나누어떨어질 때까지 반복하면, 직전에 얻은 나머지가 최대공약수이다.
- 예) gcd (12 , 3) , 몫 : 4 나머지: 0 이므로, 최대공약수(G)는 3,
AB = LG 이므로, 12 * 3 = L * 3 , 최대공배수(L) 는 12
class Solution {
public int[] solution(int n, int m) { // 3 12
int[] answer = new int[2];
int big = Math.max(n, m); // 12
int small = Math.min(n, m); // 3
answer[0] = gcd(big, small); // 최대공약수 3
answer[1] = big * small / answer[0]; // 최대공배수 12 * 3 /3 = 12
return answer;
}
// 유클리드 호제법 Method
static int gcd(int a, int b) { // 12 3
if (a % b == 0) {
return b; // 3
}
return gcd(b, a % b);
}
}🔗 문제 링크
[프로그래머스 - 최대공약수와 최소공배수]
https://programmers.co.kr/learn/courses/30/lessons/12940
ImOk👌