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

문제 링크

---

1. 아이디어

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

---

2. 복잡도

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

($x = numer1 \cdot denom2 + numer2 \cdot denom1$, $y = denom1 \cdot denom2$ — GCD를 구하는 두 값. 유클리드 호제법은 값의 크기에 비례해 스텝 수가 늘어나며, 이 문제는 $x$, $y$가 각각 $< 2 \times 10^6$, $< 10^6$로 작아 실질적으로는 상수에 가깝다.)

---

3. 코드

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

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int x = numer1 * denom2 + numer2 * denom1;
        int y = denom1 * denom2;
        int g = gcd(x, y);

        return new int[]{x / g, y / 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 x = numer1 * denom2 + numer2 * denom1;
    int y = denom1 * denom2;
    int g = gcd(x, y);

    return {x / g, y / g};
}

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

import math


def solution(numer1, denom1, numer2, denom2):
    x = numer1 * denom2 + numer2 * denom1
    y = denom1 * denom2
    g = math.gcd(x, y)

    return [x // g, y // g]

Python도 math 모듈의 math.gcd를 표준으로 제공한다.

---