[프로그래머스] 분수의 덧셈 (JAVA)

 

 

 

💡 문제 

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

 

문제 요구사항 분석:

• 입력으로 주어진 두 분수의 분자와 분모를 더한 결과를 구한다.
• 구한 결과를 기약 분수로 나타낸다.
• 기약 분수로 나타낸 결과의 분자와 분모를 순서대로 배열에 담아 return 한다.

 

해결 방법:

• 입력으로 주어진 두 분수의 분모(denominator)의 최소공배수(lcm)를 구한다.
• 최소공배수(lcm)로 각 분수의 분자(numerator)를 곱한 뒤, 더하여 새로운 분자를 구한다.
• 새로운 분자와 최소공배수(lcm)를 기약분수로 나타낸다. 이 때, 분자와 분모의 최대공약수(gcd)를 구한 뒤, 각각을 최대공약수로 나누어 준다.
•  

 

시간 복잡도:

주어진 문제는 분수의 덧셈 연산을 수행하고, 결과를 기약 분수로 나타내는 것이 요구된다. 분수의 덧셈 연산은 분모의 최소공배수를 구한 후, 두 분수의 분자를 곱하여 분모로 나누는 것으로 수행된다. 이때 최소공배수를 구하는 과정에서 O(n)의 시간이 필요하며, 분자와 분모를 곱하는 과정에서도 O(n)의 시간이 소요된다.

따라서, 주어진 문제의 시간 복잡도는 O(n)이다.

 

 

알고리즘:

1. 주어진 두 분수의 분모의 최소공배수를 구한다. 최소공배수란 두 수의 공통인 배수 중 가장 작은 수를 의미한다.
2. 최소공배수를 이용하여 각 분수의 분자를 곱한 뒤, 더하여 새로운 분자를 구한다.
3. 새로운 분자와 최소공배수를 기약분수로 나타낸다. (기약분수: 분자와 분모가 서로소인 분수) 이때, 분자와 분모의 최대공약수를 구한 뒤, 각각을 최대공약수로 나눈다.

예를 들어, 2/3과 3/4의 합을 구한다면, 먼저 3과 4의 최소공배수인 12를 구한다. 그리고 2/3을 8/12로, 3/4를 9/12로 변환한 뒤, 더해준다. 따라서, 2/3 + 3/4 = 8/12 + 9/12 = 17/12가 된다. 마지막으로, 17/12를 기약분수로 나타내면, 분자와 분모의 최대공약수를 구하는 과정을 거친다. 이 경우, 17과 12의 최대공약수는 1이므로, 17/12가 기약분수가 된다.

 

 

 

🖍 내 답안

import java.util.*;

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        // 1. 최소공배수(lcm) 계산
        int lcm = (denom1 * denom2) / gcd(denom1, denom2);

        // 2. 새로운 분자 계산
        int newNumer = numer1 * (lcm / denom1) + numer2 * (lcm / denom2);

        // 3. 기약분수로 변환
        int gcd = gcd(newNumer, lcm);
        return new int[] { newNumer / gcd, lcm / gcd };
    }

    // 최대공약수 계산 함수
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

 

 

 

import java.util.*;
import java.util.stream.*;

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int lcm = lcm(denom1, denom2);
        int newNumer = numer1 * (lcm / denom1) + numer2 * (lcm / denom2);
        int gcd = gcd(newNumer, lcm);
        return IntStream.of(newNumer / gcd, lcm / gcd).toArray();
    }

    public int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

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