[프로그래머스 / JAVA] Level 1 최대공약수와 최소공배수 (12940)
게시글
⏰ 2021-12-18 12:30:56
D O W N

D O W N
랭크 | 사용 언어 |
---|---|
Level 1 | JAVA |
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
n | m | return |
---|---|---|
3 | 12 | { 3, 12 } |
2 | 5 | { 1, 10 } |
입출력 예 #1
위의 설명과 같습니다.
입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.
두 수 n, m의 최대공약수와 최소공배수를 구하는 문제. 최대공약수만 구하면 n과 m, 최대공약수를 활용해 최소공배수를 구할 수 있다.
약수를 일일히 구해 비교하는 방법도 있지만, 유클리드 호제법을 활용하여 최대공약수를 쉽게 구할 수 있다.
유클리드 호제법
이렇게 최대공약수를 구하면, 최소공배수는 간단하게 구할 수 있다.
n과 m을 곱하고, 최대공약수로 이를 나누면 된다.
구한 두 값을 배열로 만들어 반환하면 된다.
JAVA
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
/** * 최대공약수와 최소공배수 클래스 * * @author RWB * @since 2021.12.13 Mon 19:33:08 */ class Solution { /** * 해답 반환 메서드 * * @param n: [int] 정수 1 * @param m: [int] 정수 2 * * @return [int[]] 해답 */ public int[] solution(int n, int m) { int[] answer = new int[2]; answer[0] = gcd(n, m); answer[1] = n * m / answer[0]; return answer; } /** * 유클리드 호제법 연산결과 반환 메서드 * * @param n: [int] 정수 1 * @param m: [int] 정수 2 * * @return [int] 최대공약수 */ private int gcd(int n, int m) { while (m != 0) { int r = n % m; n = m; m = r; } return n; } }
🏷️ Related Tag