최대공약수와 최소공배수

---

🔗 🔗 최대공약수와 최소공배수

문제 설명

---

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

제한 사항

---

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

입출력 예

---

입출력 예 설명

---

입출력 예 #1

위의 설명과 같습니다.

입출력 예 #2

자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

풀이

---

두 수 n, m의 최대공약수와 최소공배수를 구하는 문제. 최대공약수만 구하면 n과 m, 최대공약수를 활용해 최소공배수를 구할 수 있다.

약수를 일일히 구해 비교하는 방법도 있지만, 유클리드 호제법을 활용하여 최대공약수를 쉽게 구할 수 있다.

유클리드 호제법

1. n을 m으로 나눠 나머지 r를 구한다.
   • r이 0일 경우, 나눴던 그 수가 최대공약수가 된다.
2. n은 m으로, m은 r로 할당하여 1을 반복한다.

이렇게 최대공약수를 구하면, 최소공배수는 간단하게 구할 수 있다.

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;
	}
}