코딩테스트 연습 - 최대공약수와 최소공배수
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의
programmers.co.kr
정답(Solution)
import java.util.*;
class Solution {
public int[] solution(int n, int m) {
int[] answer = new int[2];
answer[0] = maxSame(n, m);
answer[1] = minSame(n, m);
return answer;
}
private int maxSame(int first, int second){
int result = 0;
List<Integer> iList1 = new ArrayList<>();
for(int i=1; i<=first; i++){
if(first % i == 0){
iList1.add(i);
}
}
List<Integer> iList2 = new ArrayList<>();
for(int i=1; i<=second; i++){
if(second % i == 0){
iList2.add(i);
}
}
for(int num1 : iList1){
for(int num2 : iList2){
if(num1 == num2 && result < num1){
result = num1;
}
}
}
return result;
}
private int minSame(int first, int second){
int result = 0;
int min = 0;
int max = 0;
if(first > second){
max = first;
min = second;
}else{
max = second;
min = first;
}
int minSum = min;
int maxSum = max;
while(result == 0){
if(min == max){
result = min;
return result;
}
min += minSum;
if(min > max){
max += maxSum;
}
}
return result;
}
}
분석
최대공약수는 각각의 약수들을 구한 후 공통 약수 중 가장 큰 것을 구하면 된다.
최소공배수는 작은 수를 증가시키면서 큰 수와 같아지는 경우 최소공배수이다.
최대공약수를 구하는 유클리드 호제법이 있다. 위 알고리즘을 사용하면 간단히 최대공약수를 구할 수 있고 최소공배수는 두 값의 곱을 나누면 나오기 때문에 최대공약수로 두 수의 곱을 나눠주면 된다.
수학을 알면 매우 쉽게 풀 수 있는 문제
class Solution {
public int[] solution(int n, int m) {
return new int[]{euclidean(n, m), n*m/euclidean(n,m)};
}
private int euclidean(int a, int b){
if(b == 0){
return a;
}else{
return euclidean(b, a % b);
}
}
}