https://school.programmers.co.kr/learn/courses/30/lessons/120808
class Solution {
public int[] solution(int denum1, int num1, int denum2, int num2) {
int[] answer = new int[2];
answer[0] = denum1 * num2 + denum2 * num1;
answer[1] = num1 * num2;
List<Integer> num1Cd = new ArrayList<>();
List<Integer> num2Cd = new ArrayList<>();
int sqrt1 = (int) Math.sqrt(answer[0]);
int sqrt2 = (int) Math.sqrt(answer[1]);
for (int i = 1; i <= sqrt1; i++) {
if (answer[0] % i == 0) {
num1Cd.add(i);
num1Cd.add(answer[0] / i);
}
}
for (int i = 1; i <= sqrt2; i++) {
if (answer[1] % i == 0) {
num2Cd.add(i);
num2Cd.add(answer[1] / i);
}
}
Collections.sort(num1Cd);
Collections.sort(num2Cd);
int gcd = 0;
for (int i : num1Cd) {
if (num2Cd.contains(i)) {
gcd = i;
}
}
if (gcd != 1) {
answer[0] = answer[0] / gcd;
answer[1] = answer[1] / gcd;
}
return answer;
}
}
<유클리드 호제법>
- 두 양의 정수 a,b(a>b)에 대하여 a = bq + r (0 ≤ r < b)이라 하면,
a,b의 최대공약수는 b,r의 최대공약수와 같다.
즉,
gcd(a, b) = gcd(b, r) r=0이라면, a,b의 최대공약수는 b가 된다.
# 예
gcd(12, 8) -> 12 = 8*1 + 4
-> gcd(12, 8) = gcd(8,4)
-> 8 = 4*2 + 0
-> gcd(8,4) = gcd(4,0)
-> 최대공약수는 4
활용 풀이
class Solution {
public int GCD(int num1, int num2) {
if (num1 % num2 == 0)
return num2;
return GCD(num2, num1 % num2);
}
public int[] solution(int denum1, int num1, int denum2, int num2) {
int[] answer;
denum1 *= num2;
denum2 *= num1;
answer = new int[]{denum1 + denum2, num1 * num2};
int greatestCommonDivisor = GCD(answer[0], answer[1]);
answer[0] /= greatestCommonDivisor;
answer[1] /= greatestCommonDivisor;
return answer;
}
}