[Programmers] 120808번 - 분수의 덧셈 [Java][C++]

문제 링크

---

1. 아이디어

두 분수를 통분해 더한 뒤(분자는 교차곱의 합, 분모는 두 분모의 곱), 유클리드 호제법을 활용해 최대공약수로 나눠 기약분수로 만들어줬다.

---

2. 복잡도

시간복잡도	공간복잡도
$O(\log(\min(a,b)))$	$O(1)$

$a$ = numer1×denom2 + numer2×denom1 (통분 분자), $b$ = denom1×denom2 (통분 분모)

---

3. 코드

풀이 [Java][C++]

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int g = gcd(numer1 * denom2 + numer2 * denom1, denom1 * denom2);
        return new int[]{(numer1 * denom2 + numer2 * denom1) / g, (denom1 * denom2) / g};
    }

    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

#include <numeric>
#include <vector>

using namespace std;

vector<int> solution(int numer1, int denom1, int numer2, int denom2) {
    int g = gcd(numer1 * denom2 + numer2 * denom1, denom1 * denom2);
    return {(numer1 * denom2 + numer2 * denom1) / g, (denom1 * denom2) / g};
}

---