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

문제 링크

---

1. 아이디어

분수 numer1/denom1과 numer2/denom2를 더한 값을 기약분수로 나타내, 분자와 분모를 순서대로 담은 배열을 반환하는 문제다. 먼저 $\dfrac{\text{numer1}}{\text{denom1}} + \dfrac{\text{numer2}}{\text{denom2}} = \dfrac{\text{numer1} \times \text{denom2} + \text{numer2} \times \text{denom1}}{\text{denom1} \times \text{denom2}}$ 공식대로 두 분수를 통분했다. 이렇게 구한 분수는 기약분수가 아닐 수 있으므로, 분자와 분모의 최대공약수로 두 값을 나눠 기약분수로 만들었다. 최대공약수는 유클리드 호제법으로 구하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(\log \min(P, Q))$	$O(1)$

($P$ = 통분한 분자 $\text{numer1} \times \text{denom2} + \text{numer2} \times \text{denom1}$, $Q$ = 통분한 분모 $\text{denom1} \times \text{denom2}$)

---

3. 코드

풀이 [Java][C++][Python]

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

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

Java는 표준 라이브러리에 정수 GCD 함수가 없어 유클리드 호제법을 직접 구현했다.

#include <bits/stdc++.h>
using namespace std;

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

C++17부터는 <numeric>(<bits/stdc++.h>에 포함됨)의 std::gcd를 바로 쓸 수 있다.

import math


def solution(numer1, denom1, numer2, denom2):
    p = numer1 * denom2 + numer2 * denom1
    q = denom1 * denom2
    g = math.gcd(p, q)
    return [p // g, q // g]

Python은 math.gcd를 표준으로 제공한다.

---