(프로그래머 코딩 테스트) 분수의 덧셈(자바)

문제

매개 변수 numer1 및 denom1, 첫 번째 분수의 분자 및 분모, 두 번째 분수의 numer2, denom2, 분자 및 분모로 제공됩니다. 두 분수의 합이 기약 분수로 표현될 때 분자와 분모를 순서대로 포함하는 배열을 반환하도록 solve 함수를 완성하십시오.

제한

• 0 < 숫자1, 분모1, 숫자2, 분모2 < 1,000

I/O 예시

class Solution {
    static int gcd(int a, int b) {
            if (a % b == 0) {
                return b;  
            } return gcd(b, a % b);
            }
    public int() solution(int numer1, int denom1, int numer2, int denom2) {
        int() answer = new int(2);
        int sum1 = ((numer1 * denom2) + (numer2 * denom1));
        int sum2 = (denom1 * denom2);
       
        answer(0) = sum1 / gcd(sum1, sum2);
        answer(1) = sum2 / gcd(sum1, sum2);
        return answer;
    }
}

이 문제를 풀려면 두 가지를 알아야 합니다. 분수를 계산하는 방법과 최대 공약수를 찾는 방법. 수학책을 집어들어도 지도가 흐릿하고 분수의 존재조차 잊고 있었다. 그래도 이 부분은 상당히 쉽습니다.

위의 코드에서 sum1과 sum2에 해당하는 부분입니다. 그러나 문제는 위의 공식이 단순한 공식이지 문제에서 원하는 기약분수가 아니라는 점입니다. 기약분수(irreducible fraction)의 사전적 정의는 “분모와 분자의 공약수가 1뿐이어서 더 이상 줄일 수 없는 분수”입니다. 분자와 분모의 최대공약수(gcd)로 나누어야 합니다. 최대 공약수의 사전적 정의는 “두 개 이상의 정수의 공약수 중 가장 큰 수”입니다. 최대 공약수가 아닌 다른 공약수로 나누면 이것은 단지 약수일 뿐 약수라고 할 수 없습니다.

요점으로 돌아가서 재귀 함수를 사용했습니다. “Euclidean Algorithm”, “Biginteger” 및 “Brute Force” 방법도 있습니다. 사실 내가 작성한 재귀 함수도 유클리드 알고리즘에 속하는 것 같지만 완전히 확신할 수는 없다. 아직 배울 게 좀 있는 것 같습니다.

유클리드 알고리즘은 최대 공약수 알고리즘이며 두 숫자 a와 b의 gcd는 b와 a%b의 gcd가 같다는 원리를 사용합니다. 다음 코드는 유클리드 알고리즘과 루프를 사용한 코드입니다.

public static int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

다음 코드는 BigInteger 클래스를 사용하는 메서드입니다. 이 클래스는 편의를 위해 gcd() 메서드를 제공합니다. 장단점은 모르겠고 나중에 알게되면 추가하겠습니다.

import java.math.BigInteger;

public static BigInteger gcd(BigInteger a, BigInteger b) {
    return a.gcd(b);
}

아래 코드는 무차별 대입 방법입니다. 이 방법은 두 숫자의 모든 약수와 최대 공약수를 찾습니다. “모든” 숫자를 찾는 방법과 마찬가지로 시간 복잡도가 O(n)이기 때문에 큰 숫자에는 사용하지 않는 것이 효율적입니다.

public static int gcd(int a, int b) {
    int gcd = 1;
    for (int i = 1; i <= a && i <= b; i++) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

최대 공약수를 찾는 방법에는 여러 가지가 있습니다. 유클리드 알고리즘만 알고 있어도 별 문제는 없지만, 다양하게 구현할 수 있다면 언젠가는 쓰일 수 있을 것이다.

문제를 풀었을 때 매우 슬펐습니다. 2일차 치고는 좀 악랄했던 것 같은데… .