문제

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

• 재귀를 활용해 유클리드 알고리즘을 사용하여 최대공약수를 구한 후 적용