https://programmers.co.kr/learn/courses/30/lessons/12940?language=java
풀이
최대공약수는 두 수 중 공통된 약수 중 가장 큰 자연수,
최소공배수는 두 수의 공통된 배수중 가장 작은 자연수를 의미한다.
때문에 n과 m중 더 작은 수부터 1씩 줄여나가며 둘 다 나머지가 0이 되는 수를 최대공약수로,
n*m을 최대공약수로 나눠준 수를 최소공배수로 넣어주었다.
class Solution {
public int[] solution(int n, int m) {
int[] answer = {0,0};
for(int i=Math.min(n,m);i>0;i--){
if ((n%i==0)&&(m%i==0)){
answer[0] = i;
answer[1] = (n*m)/i;
break;
}
}
return answer;
}
}
유클리드 호제법과 재귀식을 사용하여 풀기
최대공약수를 구하는 재귀함수 gcd()를 만들었다.
함수에는 유클리드 호제법(최대공약수를 구하는 알고리즘)을 적용했다.
유클리드 호제법의 설명과 알고리즘 풀이는 아래의 포스팅을 참고.
유클리드 호제법이란 서로 상대방의 수를 나누어 최대공약수를 구하는 방법으로
a%b = r(a>b) 일 때, a,b와 b,r의 최대공약수는 같다.
즉, 재귀함수로 만들어 반복해서 나눴을 때, 나머지가 0이 되는 시점의 나누는 수가 a,b의 최대공약수이다.
class Solution {
public int[] solution(int n, int m) {
int[] answer = {0,0};
answer[0]=gcd(Math.max(n,m), Math.min(n,m)); // 최대공약수
answer[1]=(n*m)/answer[0]; // 최소공배수
return answer;
}
// 유클리드 호제법을 사용해 최대공약수 구하는 재귀함수
public int gcd(int a, int b){
if(b==0) return a;
return gcd(b,a%b);
}
}
'Algorithm & Data Structure > 프로그래머스' 카테고리의 다른 글
[JAVA] 프로그래머스 : 자릿수 더하기 (0) | 2022.01.21 |
---|---|
[JAVA] 프로그래머스 : 약수의 합 (0) | 2022.01.21 |
[JAVA] 프로그래머스 : 정수 제곱근 판별 (0) | 2022.01.21 |
[JAVA] 프로그래머스 : 소수찾기 (0) | 2022.01.21 |
[JAVA] 프로그래머스 1단계 5문제 (0) | 2022.01.19 |