👀 문제
https://programmers.co.kr/learn/courses/30/lessons/12940
👊 도전
1. 설계
- 유클리드 호제법을 이용하여 최대공약수를 구한다.
- 최소공배수는 두 수의 곱에 최대공약수로 나눈 값이다.
2. 구현 (성공 코드)
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
/**
*
* @author HEESOO
*
*/
class Solution {
public int[] solution(int n, int m) {
int[] answer = {};
answer=new int[2];
int temp;
if(m<n){//m이 큰수, n은 작은수
temp=m;
m=n;
n=temp;
}
answer[1]=m*n;
int r;
while(true){
r=m%n;
if(r==0){
answer[0]=n;
break;
}
else{
m=n;
n=r;
}
}
answer[1]/=answer[0];
return answer;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 유클리드 호제법으로 최대공약수를 구한다.
- m은 큰 수, n은 작은 수가 들어가도록 한다.
- m%n==0이면 최대공약수는 n이다.
- m%n==r(r!=0)이라면 최대공약수는 r과 b의 최대공약수와 같으므로 m에는 n, n에는 r을 넣고 다시 m%n==0이 될 때까지 반복한다.
- 최소공약수는 두 수의 곱에 최대공약수로 나눈 값이다.
- m과 n은 while문을 돌면서 값이 계속 바뀌므로 while문을 돌기 전 두 수의 곱을 answer[1]에 저장해둔다.
- 최대공약수를 구하고 난 후 answer[1]의 값에 최대공약수로 나눠 최소공배수르 구한다.
👏 해결 완료!
간단한 문제였지만 수학적 지식이 필요했다. 유클리드 호제법을 알게 되었다.